Note: This method assumes that the graph doesnβt contain any self-loops.
/**
* @param {number} n
* @param {number[][]} adj
* @return {number}
*/
// with disjoint set
// undirected graph
// no self loop
class Solution {
detectCycle(n,adj){
/**
* n = 5;
* adj =
* [
* [ 2, 3, 4 ],
* [ 3 ],
* [ 0, 4 ],
* [ 0, 1 ],
* [ 0, 2 ]
* ];
*
*/
// console.log(n, adj);
this.parents = [];
this.ranks = [];
for (let i = 0; i < n; i++) {
this.createSet(i);
}
const visited = {};
for (let i = 0; i < n; i++) {
const here = i;
const arr = adj[i];
for (const there of arr) {
const hasSameRoot = this.unionIfNotConnected(here, there);
if (!hasSameRoot) {
visited[there] = here;
continue;
}
// hasSameRoot === true
// check reverse is visited directly, if true, directly connected then ok
// μ΄μ μ there -> here λ‘ μ°κ²°λ μ μ΄ μλμ?
// 0 -> 1, 1 -> 0 μΌλ‘ λ λ² λ³κ²½ λλκ² μ μ
// 2 -> 4λ‘ κ°λ κ°μ μΈλ° root κ° κ°μλ° 4 -> 2 κ° μ‘΄μ¬ νμ§ μμΌλ©΄? cycle
const isDirectlyConnected = visited[here] === there;
// console.log(':: ', here, there, hasSameRoot, visited, isDirectlyConnected);
if (!isDirectlyConnected) {
return 1;
}
}
}
return 0;
}
createSet(v) {
this.parents[v] = v;
this.ranks[v] = 1;
}
find(v) {
if (this.parents[v] === undefined)
return;
// root found
let root = v;
while (root !== this.parents[v]) {
root = this.parents[v];
}
// pass compression
while (root !== v) {
const newV = this.parents[v];
this.parents[v] = root;
v = newV;
}
return root;
}
unionIfNotConnected(v1, v2) {
const root1 = this.parents[v1];
const root2 = this.parents[v2];
if (root1 === undefined || root2 === undefined) {
throw new Error('illegal arguments exception');
return;
}
if (root1 === root2) {
return true;
}
const rank1 = this.ranks[root1];
const rank2 = this.ranks[root2];
if (rank1 >= rank2) {
this.parents[root2] = root1;
this.ranks[root1] += this.ranks[root2];
} else {
this.parents[root1] = root2;
this.ranks[root2] = this.ranks[root1];
}
return false;
}
}