Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree LeetCode solution in JavaScript

1
/**
2
 * @param {number} n
3
 * @param {number[][]} edges
4
 * @return {number[][]}
5
 */
6
var findCriticalAndPseudoCriticalEdges = function (n, edges) {
7
  // find and union utils
8
  const find = (x, parent) => {
9
    if (parent[x] === -1) {
10
      return x;
11
    }
12
    const y = find(parent[x], parent);
13
    parent[x] = y;
14
    return y;
15
  };
16
  const union = (a, b, parent) => {
17
    a = find(a, parent);
18
    b = find(b, parent);
19
    if (a === b) {
20
      return false;
21
    }
22
    parent[a] = b;
23
    return true;
24
  };
25

26
  // sort and group edges by cost
27
  const map = {};
28
  edges.forEach(([a, b, cost], i) => {
29
    map[cost] = map[cost] || [];
30
    map[cost].push([a, b, i]);
31
  });
32
  const costs = Object.keys(map).sort((a, b) => a - b);
33

34
  // check by group
35
  const check = (edges, parent) => {
36
    let nextParent;
37
    let count;
38

39
    // travel with a skipped point
40
    // if skip === -1, skip nothing and update count and nextParent.
41
    const travel = (skip) => {
42
      const p = [...parent];
43
      const result = [];
44
      edges.forEach(([a, b, i]) => {
45
        if (i === skip) {
46
          return;
47
        }
48
        if (union(a, b, p)) {
49
          result.push(i);
50
        }
51
      });
52
      if (skip === -1) {
53
        count = result.length;
54
        nextParent = p;
55
      }
56
      return result;
57
    };
58

59
    // get default count and nextParent.
60
    travel(-1);
61

62
    // special case: there is only one edge in this group
63
    if (edges.length === 1) {
64
      if (count === 0) {
65
        return [[], [], 0, parent];
66
      }
67
      return [[edges[0][2]], [], 1, nextParent];
68
    }
69

70
    // aList -> critical, bList -> pseudo
71
    const aList = {};
72
    const bList = {};
73
    edges.forEach(([a, b, i]) => {
74
      if (find(a, parent) === find(b, parent)) {
75
        return;
76
      }
77
      const result = travel(i);
78
      result.length < count ? (aList[i] = true) : (bList[i] = true);
79
    });
80
    return [Object.keys(aList), Object.keys(bList), count, nextParent];
81
  };
82

83
  // init traversal state
84
  const critical = [];
85
  const pseudo = [];
86
  let count = 0;
87
  let parent = new Array(n).fill(-1);
88

89
  // travel by cost group until all points visited
90
  for (let i = 0; i < costs.length; i++) {
91
    const [aList, bList, newCount, nextParent] = check(map[costs[i]], parent);
92
    critical.push(...aList);
93
    pseudo.push(...bList);
94
    count += newCount;
95
    parent = nextParent;
96
    if (count === n - 1) {
97
      break;
98
    }
99
  }
100

101
  return [critical, pseudo];
102
};