Longest Cycle in a Graph LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} edges
3
 * @return {number}
4
 */
5
function getCycleTopology(edges) {
6
  const indeg = new Array(edges.length).fill(0);
7
  const queue = [];
8
  const map = {};
9
  for (const src in edges) {
10
    const des = edges[src];
11
    if (des >= 0) {
12
      indeg[des]++;
13
    }
14
    map[src] ? map[src].push(des) : (map[src] = [des]);
15
  }
16
  for (const node in indeg) {
17
    if (indeg[node] === 0) {
18
      queue.push(node);
19
    }
20
  }
21
  while (queue.length > 0) {
22
    const node = queue.shift();
23
    for (const connectedNode of map[node]) {
24
      if (connectedNode !== -1) {
25
        indeg[connectedNode]--;
26
        if (indeg[connectedNode] === 0) {
27
          queue.push(connectedNode);
28
        }
29
      }
30
    }
31
  }
32
  return indeg;
33
}
34
class DisjointSet {
35
  constructor(n) {
36
    this.n = n;
37
    this.root = new Array(n).fill(0).map((_, i) => i);
38
    this.rank = new Array(n).fill(1);
39
  }
40
  find(x) {
41
    if (x === this.root[x]) return x;
42
    return (this.root[x] = this.find(this.root[x]));
43
  }
44
  union(x, y) {
45
    const x_root = this.find(x);
46
    const y_root = this.find(y);
47

48
    if (this.rank[x_root] < this.rank[y_root]) {
49
      [this.rank[x_root], this.rank[y_root]] = [
50
        this.rank[y_root],
51
        this.rank[x_root],
52
      ];
53
    }
54
    this.root[y_root] = x_root;
55
    if (this.rank[x_root] === this.rank[y_root]) this.rank[x_root]++;
56
  }
57
  _getGroupsComponentCounts() {
58
    let groups = {};
59
    for (const node of this.root) {
60
      const node_root = this.find(node);
61
      groups[node_root] = groups[node_root] + 1 || 1;
62
    }
63
    return groups;
64
  }
65
  getLongestGroupComponentLength() {
66
    let longestLength = 1;
67
    const lengths = this._getGroupsComponentCounts();
68
    for (const length of Object.values(lengths)) {
69
      if (length > 1) {
70
        longestLength = Math.max(longestLength, length);
71
      }
72
    }
73
    return longestLength > 1 ? longestLength : -1;
74
  }
75
}
76
var longestCycle = function (edges) {
77
  const djs = new DisjointSet(edges.length);
78
  let res = -1;
79

80
  // topology sort results topology array.
81
  // component with greater than 0 is cyclic component.
82
  // now we need to get groups of cycle since we can't distinguish each cycles with current datas.
83
  const cycleComponent = getCycleTopology(edges);
84

85
  //with edges info and cycle component data, we can now distinguish each cycle group by union finde
86
  // because each cycle r independent with each other.
87
  for (const src in edges) {
88
    const des = edges[src];
89
    if (cycleComponent[src] && cycleComponent[des]) {
90
      djs.union(src, des);
91
    }
92
  }
93
  res = djs.getLongestGroupComponentLength();
94
  return res;
95
};