Kruskal's algorithm

help
1

In detecting a cycle in a graph using union by rank and path compression, if we use adjacency list for undirected graph and solve like :-

int isCycle(vector adj[], int V)
{
for (int i = 0; i < V; i++) {
for (int j = 0; j < adj[i].size(); j++) {
int x = find(i);
int y = find(adj[i][j]);
if (x == y)
return 1;
_union(x, y);
}
}
return 0;
}

Each edge will be run in the loop twice. If graph is like:-

vertices = {0,1,2}
edges = { (0,1), (0,2), (1,2) }

Then for first iteration i = 0, edge 0-1 and 0-2 is evaluated then for 2nd iteration, cycle is detected for i = 1, for edge 1-0 (0-1 and 1-0 for an undirected graph) without moving to edge 1-2.

Above code would show cycle for edges = { (0,1), (0,2) } also which does not have cycle.

So how can we use union find algorithm for cycle detection using adjacency list for undirected graph ?

2

your code is also finding the cycle of length 2, but we don’t consider cycle of length 2 so write your code like this:
int isCycle(vector adj[], int V)
{
map<pair<int,int>,bool> mp;
for (int i = 0; i < V; i++) {
for (int j = 0; j < adj[i].size(); j++) {
int u = i;
int v = adj[i][j];
if(u > v)
swap(u,v);
if(mp.find({u,v}) != mp.end())
continue ;
mp[{u,v}] = 1;
int x = find(i);
int y = find(adj[i][j]);
if (x == y)
return 1;
_union(x, y);
}
}
return 0;
}

I think this will work.

3

Thanks, it worked. It was the code from geeksforgeeks. I think some change is needed there Union-Find Algorithm | (Union By Rank and Find by Optimized Path Compression) - GeeksforGeeks

4

Actually on geeks, while creating the adjacency matrix if they are adding edge (u -> v) then they are not adding (v -> u) in the matrix so their code will work and no need to use map for checking of duplicate edge as I did in your code. So no need to worry just understand the concept of Union Find. Good luck.

5

okay…thanks :grinning: