Disjoint Sets

Question 1

find method

Answer 1

// Finds the representative of the set that i
// is an element of.
int find(int i) 
{
    // If i is the parent of itself
    if (Parent[i] == i) 
    {
        // Then i is the representative 
        return i;
    }
    else
    { 
        // Recursively find the representative.
        int result = find(Parent[i]);

        // We cache the result by moving i’s node 
        // directly under the representative of this
        // set
        Parent[i] = result;

        // And then we return the result
        return result;
     }
}

Question 2

union method

Answer 2

// Unites the set that includes x and the set
    // that includes x
    void union(int x, int y)
    {
        // Find representatives of two sets
        int xRoot = find(x), yRoot = find(y);

        // Elements are in the same set, no need
        // to unite anything.
        if (xRoot == yRoot)
            return;

        // If x's rank is less than y's rank
        if (rank[xRoot] < rank[yRoot])

            // Then move x under y  so that depth
            // of tree remains less
            parent[xRoot] = yRoot;

        // Else if y's rank is less than x's rank
        else if (rank[yRoot] < rank[xRoot])

            // Then move y under x so that depth of
            // tree remains less
            parent[yRoot] = xRoot;

        else // if ranks are the same
        {
            // Then move y under x (doesn't matter
            // which one goes where)
            parent[yRoot] = xRoot;

            // And increment the result tree's
            // rank by 1
            rank[xRoot] = rank[xRoot] + 1;
        }
    }

Question 3

find cycle in graph

Answer 3

// The main function to check whether a given graph
    // contains cycle or not
    int isCycle( Graph graph)
    {
        // Allocate memory for creating V subsets
        int parent[] = new int[graph.V];

        // Initialize all subsets as single element sets
        for (int i=0; i