Union-Find Algorithm | Set 1 (Detect Cycle in a an Undirected Graph) | GeeksforGeeks

Union-Find Algorithm | Set 1 (Detect Cycle in a an Undirected Graph) | GeeksforGeeks
Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. 
For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.
Code from http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

int find(struct subset subsets[], int i)

{

    // find root and make root as parent of i (path compression)

    if (subsets[i].parent != i)

        subsets[i].parent = find(subsets, subsets[i].parent);

    return subsets[i].parent;

}

// A function that does union of two sets of x and y

// (uses union by rank)

void Union(struct subset subsets[], int x, int y)

{

    int xroot = find(subsets, x);

    int yroot = find(subsets, y);

    // Attach smaller rank tree under root of high rank tree

    // (Union by Rank)

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

        subsets[yroot].parent = xroot;

    // If ranks are same, then make one as root and increment

    // its rank by one

    else

    {

        subsets[yroot].parent = xroot;

        subsets[xroot].rank++;

    }

}

// The main function to check whether a given graph contains cycle or not

int isCycle( struct Graph* graph )

{

    int V = graph->V;

    int E = graph->E;

    // Allocate memory for creating V sets

    struct subset *subsets =

        (struct subset*) malloc( V * sizeof(struct subset) );

    for (int v = 0; v < V; ++v)

    {

        subsets[v].parent = v;

        subsets[v].rank = 0;

    }

    // Iterate through all edges of graph, find sets of both

    // vertices of every edge, if sets are same, then there is

    // cycle in graph.

    for(int e = 0; e < E; ++e)

    {

        int x = find(subsets, graph->edge[e].src);

        int y = find(subsets, graph->edge[e].dest);

        if (x == y)

            return 1;

        Union(subsets, x, y);

    }

    return 0;

}

struct Edge

{

    int src, dest;

};

struct Graph

{

    // V-> Number of vertices, E-> Number of edges

    int V, E;

    // graph is represented as an array of edges

    struct Edge* edge;

};

Note that the implementation of union() and find() is naive and takes O(n) time in worst case. These methods can be improved to O(Logn) using Union by Rank or Height.
Read full article from Union-Find Algorithm | Set 1 (Detect Cycle in a an Undirected Graph) | GeeksforGeeks