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 ?