Detect cycle in undirected graph
Given an undirected graph, check if there is a cycle in it or not.
For example below graph has cycles as 3>6>5>3, 1>4>3>6>2>1

Graph with cycle 
Analysis
Simple definition of a cycle in undirected graph would be : If while traversing graph, we reach at a node which we have already traversed to reach current node, then there is a cycle in graph.
How can we detect the above condition? It’s simple application of Depth First Search.
Do depth first traversal of a graph, if we detect any back edge while traversing, then there is a cycle. Back edge in a graph is an edge which is from a decedent to ancestor. For example in above graph, edge from 2 to 1 is a back edge.
While depth first traversing a graph, keep track of the nodes which are on the stack at present. If there is an edge from current node to any one of the node which is on recursion stack, we say cycle is detected in graph.
Complexity Analysis
Complexity of algorithm to find cycle in graph code is equal to complexity of DFS which is O(V+E) where V is number of vertices and E is number of edges.
Detecting cycles in graph using disjoint sets
Another method to detect cycle in an undirected graph is UnionFind method. To understand that method, we need to first understand a data structure called disjointset data structure.
It is a data structure, which keeps track of all the sets of elements partitioned in disjoint subset. Subsets are said to be disjoint if there is intersection between them is NULL. For example set {1,2,3 } and {4,5,6 } are disjoint sets, but {1,2,3 } and {1,3,5} are not.
Another important thing about disjoint set is that every set is represented by a member of that set called as representative.
There are some operations which are useful on this data structure:
1. Make Set : creates a new set with one element {x}
2. Union : Merges two sets containing X and Y and destroys the original sets.
3. Find : Returns the representative of the set which element belongs to.
Let’s take an example and see how it can be used to detect cycle in graph.
Principle here is that if two nodes forming an edge are in same disjoint set, then there is a cycle in graph.
Make set will create a set with each node with representative element as 1, which means there is only one element in each disjoint subset. Now one by one we check each edge and update our data structure accordingly. For edge 01, both are in different subsets, we need to merge them together. So sets become {0,1} and {2}. Representative of set {0,1} be {1}. Now consider another edge, 12. Node 1 belongs to set represented by 1 and 2 belongs to set represented by 1. Both are different subsets, we will merge them together. So set becomes {0,1,2} represented by 2.
Now take edge 02, where 0 and 2 are in set which is represented by 2, hence there is a cycle in the graph.
How can we implement it? There are two ways to do so. One is to have a linked list of all elements of a set for each set. Each element in turn points to the representative element. So find operation will be O(1), however union or merge operation will be O(N) as we need to modify representative element in each element of the list.
Other method is to use array. This auxiliary array stores the parent of node i at array[i]. Initially all elements in array are 1. Now whenever we merge two set, we update the corresponding index with representative element.
Find operation
function Find(x)
if x.parent == 1
return x
else
return Find(x.parent)
function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)
xRoot.parent := yRoot
Make set operation
function MakeSet(x)
x.parent := 1
Code