Hello friends! And, welcome to GeeksforGeeks. In this tutorial we are going to cover Cycle

Detection in an Undirected graph using the Union-Find algorithm. So first we see, Disjoint-set data structure. It is basically a data structure which help

us keep track of a set of elements partitioned into a number of disjoint subsets. So if we have N elements partitioned into

subsets, it will keep track of connectivity of each element in a particular subset and

also connectivity of subsets with each other. Here you can see the three sets we have. These are disjoint set as they have no elements

in common or we can say that their intersection with each other is an empty set. So this disjoint-set supports two operations, The first is the Union() operation and, the

other one is Find() operation. So if we apply these operations on these 3

sets, the Union operation will join two subsets into a single subset. i.e Union of S1 and S2 will give us a set

containing elements of set S1 and elements of set S2. Here you can see how the two sets have merged

into one. Next we can use Find() operation to determine

which subset a particular element is in. So if we say Find(B), it will look into the

universe of sets and give us S1,similarly Find(D) will again give us S1 and Find(Z)

will give us S3. Now that we have seen how Union() and Find()

works lets see how we can use them to detect a cycle in an undirected graph. So the idea that we are going to use is that

for each unvisited edge, we make subsets using both the vertices of the edge. If both the vertices belong to the same subset

we say that we have found a cycle. Letís see, how the pseudo-code for this would

look like. Here is the code for our idea. We visit all edges one by one and for both

the vertices of the edge we use Find() operation to check which subset it belongs to. If they belong to same subset we say that

a cycle has been detected, else we do a Union() of the sets they belong

to. We’ll try using this algorithm on a sample

graph and see if it works. Here is our cyclic graph on which we will

run this algorithm. So we have these 5 nodes as shown and also

we have a parent array the entries of which are initially fix to -1. So this parent array basically help us connect

the elements that belongs to the same set, the working of this will be soon clear to

you. Initial values of -1 here means that each

element is the representative of its own set or root of its own tree. See this diagram. Here you can see how each element says that

it represents its own set, so in total we have these 5 different sets. Now recall the algorithm that we have seen

previously. We start by visiting edges. Letís begin with this edge connecting node

0 and 1. We do Find() operation on node 0 and 1. So Find(0) is 0, as 0 is representative of

its own set and Find(1) is 1 as 1 is representing its own set. Since both belong to different subsets, we

do a Union() operation and merge both the subsets. Union(0,1) would give us a set having both

{0,1}. Now here comes the use of parent array. If we make 1 as parent of 0, it can help us

track both the element of the set. So 1 is the parent of 0 and, this set is represented

by 1. We then take the next edge, letís have this

edge connecting node 0 and 2. We do Find(0) and Find(2), which comes out

to be 1 and 2 respectively. See why Find(0) is 1 is because it belongs

to a set which is represented by 1. And Find(2) is 2 because it is represented

by 2 itself. Now since they belong to different subsets,

we do a Union() operation on the two subsets. Union(1,2) will look like this. Look at the parent array, 1 is the parent

of 0, 2 is the parent of 1 and then 2 is given the task to represent this subset. Also we have 3 subsets now. One having {0,1,2} represented by 2, subset

with {3} represented by 3 and subset {4} represented by 4 itself. So again we take an edge. We choose edge connecting 1 and 3. We do Find(1) and it gives 2, and Find(3)

which gives 3. Since both belong to different subsets, we

do a union of the two sets. Union(2,3) will be like this and the merged

set would be represented by 3. Also notice the change in parent array. Now we are only left with two subsets. Next we take this edge connecting node 1 and

4. We do Find(1) and it gives 3, and Find(4)

which gives 4. Since both belongs to different subsets, we

do a union of the two sets. Union(3,4) will be like this and the merged

set would now be represented by 4. We also make 4 the parent of the node 3. Now we are only left with a single set. We now choose this last edge connecting node

3 and 4. We do Find(3) and it gives 4 , and Find(4)

which gives 4. Since both 3 and 4 belong to the same set,

we say that we have found a cycle and with this we can stop our algorithm. Here we see the implementation of what we

have discussed so far. This code on cycle-detection in undirected

graph has been taken from GeeksforGeeks. This isCycle() function takes a graph as input. It creates a parent array and also initialize

each entry to -1. Next it takes each edge one by one and then

do a Find() operation on the vertices connected by this edge. If Find() of both vertices comes out to be

same, we return 1 or true else we do Union() on both the sets to which

they belong. Here we have an implementation of Find() and

Union() operation. These are the general functions and are used

in various application of disjoint-set. So now we wrap up this tutorial. If you have any doubts or suggestions please

leave them in the comment section below. Thanks for watching!

very well explained.. really superb..

great explanation..but dude you're too slow. Please try to speak a bit faster! (otherwise, half the people will sleep while watching your videos).

Since it is un-directed graph, does this algorithm work if the edge-list contains both the edges between (u, v) ?

SIR FIND(1)=2,FIND(4)=4( HONA CHAHIYA) PLZ..CORRECT IT SIR

Thank you so much! It is a very clear explanation.

In Union function, we are already passing the sets in which the vertices of a particular edge belongs to. But in Union function, we are again calculating their parents in "xset" and "yset". I think this operation is unnecessary in Union function. Please correct me if I am wrong

Plz explain by tracing find and union functions with an example

What happens if th graph is directed? What changes do I have to add/remove to the algorithm union/find?

Sir what will happen if 3 and 4 will not contain an edge in that situation find(3)=find(4)=4 so it shows a cycle although there is no cycles

Video contributed by illuminati wtf?

Very nice video

Thank you very much for posting this video. It's phenominally useful.

Beautiful explanation.

time complexity of the algorithm should also be discussed