CareerCup

Hi ,

There are many algorithm Which uses union of vertex to form connected components in a graph .

Example : kruskal's algorithm and prims algorithm .

You can go through these and easily find out how Union of 2 vertex can be done so easily .

You can use disjoint sets which has 3 operations - MakeSet, FindSet, UnionSet.
UnionSet takes two vertex of the graph and and combine them in one vertex. E.g when you run union operation on a edge (A-B) you are effectively creating a representative of the set.
E.g Say
union(A, B) => A
union(B,C) => A
union(C,D) => A
union (B,Z) => A

The union operation can be maintained in a tree like structure where two nodes are inserted in a tree and one becomes the root.
Before adding any nodes in a tree you need to run findset operation on each node to find out what is the node that is representing that vertex.
e.g To do union(A,B) do a findSet(A) = A, and then do findSet(B) = B.
Since they both are in a unique set anyone can become root and other becomes a child node. Say A is the root.
Now union(B,C) => findSet(B) = A, and then do findSet(C) = C.

If you apply union by rank operation A gets priority to maintain the root, and C becomes a child node of A.
So union(B,C) = A.

FindSet(v) will take any given vertex v in the tree and will trace it to its root and return the root node.