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

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. This method assumes that graph doesn’t contain any self-loops.
We can keeps track of the subsets in a 1D array, lets call it parent[].

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.

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;

};

int find(int parent[], int i)

{

    if (parent[i] == -1)

        return i;

    return find(parent, parent[i]);

}

// A utility function to do union of two subsets

void Union(int parent[], int x, int y)

{

    int xset = find(parent, x);

    int yset = find(parent, y);

    parent[xset] = yset;

}

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

int isCycle( struct Graph* graph )

{

    // Allocate memory for creating V subsets

    int *parent = (int*) malloc( graph->V * sizeof(int) );

    // Initialize all subsets as single element sets

    memset(parent, -1, sizeof(int) * graph->V);

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

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

    // cycle in graph.

    for(int i = 0; i < graph->E; ++i)

    {

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

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

        if (x == y)

            return 1;

        Union(parent, x, y);

    }

    return 0;

}

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