-
Notifications
You must be signed in to change notification settings - Fork 0
/
count-unreachable-pairs-of-nodes-in-an-undirected-graph.js
63 lines (50 loc) · 1.71 KB
/
count-unreachable-pairs-of-nodes-in-an-undirected-graph.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/
const countPairs = (numNodes, edges) => {
const parents = Array(numNodes);
for (let index = 0; index < numNodes; index++)
parents[index] = index;
for (let edge of edges)
union(edge, parents);
const componentCounts = countComponents(parents);
return pairs(componentCounts, numNodes);
}
const union = (edge, parents) => {
const [start, end] = edge;
const startParent = parent(start, parents);
const endParent = parent(end, parents);
if (startParent === endParent) return;
const smallerParent = Math.min(startParent, endParent);
const largerParent = Math.max(startParent, endParent);
parents[largerParent] = smallerParent;
}
const parent = (node, parents) => node === parents[node] ? node : parent(parents[node], parents);
const countComponents = (parents) => {
const result = [];
for (let node of parents) {
const component = parent(node, parents);
result[component] ||= 0;
result[component]++;
}
return result;
}
const pairs = (componentCounts, numNodes) => {
let numPairs = 0;
for (let count of componentCounts) {
if (!count) continue;
numNodes -= count;
numPairs += count * numNodes;
}
return numPairs;
}
let numNodes = 11;
let edges = [[5,0],[1,0],[10,7],[9,8],[7,2],[1,3],[0,2],[8,5],[4,6],[4,2]];
let expected = 0;
let actual = countPairs(numNodes, edges);
console.assert(expected === actual, '%o', { numNodes, edges, expected, actual });
numNodes = 100000;
edges = [];
expected = 4999950000;
console.time('performance');
actual = countPairs(numNodes, edges);
console.timeEnd('performance');
console.assert(expected === actual, '%o', { numNodes, edges, expected, actual });