Disjoint Set Union | Graph | With Implementation

 

Disjoint Set Union

Disjoint Set Union (DSU) is a data structure that is used to maintain elements in groups.

Uses: Used in graph to know whether two nodes belong to the same component or not. Also used in the Kruskal algorithm.

It has two different operations namely:

1.  find_parent( ) 

2. merge ( ) or union ( ).

An efficient implementation is done by Union/merge by Rank and Path Compression.

How we do it:

Finding Parent:

In the starting, we make a parent array and the node itself is the parent. par[x] will have the parent of x. So how will the code look like:

int find_parent( int x ) {

    if( par[x] = = x )

    return x;

    return find_parent ( par[x] );

}

Time Complexity: O ( N )

Space Complexity: O ( N )

We can optimise this with path compression. In path compression we are going to make small change in the code. After finding the parent of a connected component we are going to assign it as parent of all the elements in the path we have traversed. 

int find_parent( int x ) {

    if( par[x] = = x )

    return x;

    return par[x] = find_parent ( par[x] ); //assing it to the element x 

}

Time Complexity: O ( log N )

Space Complexity: O ( N )

The amortized complexity of the algorithm is O ( log N ) where N is the size of the component. 

Merging Two Groups:

If we have to merge two groups we just need make parent of one group as the parent of the parent other group.

Lets us see it through image.

void merge( int x, int y){

    int px = find_parent( x );

    int py = find_parent ( y );

    par[ px ] = py;

}

Time Complexity: O ( N ) ( if not using path compression ) & O ( log N ) if  using path compression 

Space Complexity: O ( N )

The time complexity also depends on the function find_parent(_). The merge function above is not optimal as it may lead to formation of long paths. So, to reduce it we have two ways:

1. Merge by Size

2. Merge by Rank

Merge by Size:

In this method we will make the parent of the larger size group as the parent of smaller size group also. This will prevent in making long paths. 

In this par [ x ] stores the parent of x if x is not the parent ( or root ) of the group and if x is the parent( root ) of the whole component then it will store the negative size of the group. This will help us in saving space.

Code:

int find_parent ( int v ) {

    if( par [ v ] < 0 ) return v;

        return par [ v ] = find_parent ( par [ v ] ) ;

}

void merge( int x, int y ){

    if ( ( x = find_parent ( x ) )= = ( y = find_parent( y ) ) ) return ;

    if ( par [ y ] < par [ x ] )

    swap ( x , y );

    par[ x ] + = par [ y ];

    par [ y ] = x;

}

Time Complexity: O ( log N ) ( if path compression is not used and O ( 1 ) if used )

Space Complexity: O ( N )

Merge by Rank:

This is almost same as the merge by size instead of merging by size we merge by depth of the group which means the longest path in a group. Here we make the parent of group with greater depth as the parent of parent of of group with smaller depth.

In this par[ x ] stores the parent if x is not the parent and if x itself is parent then it stores the negative of rank ( depth ) of the group. This helps us saving space.

int find_parent ( int v ) {

    if( par [ v ] < 0 ) return v;

        return par [ v ] = find_parent ( par [ v ] ) ;

}

void merge( int x, int y ){

    if ( ( x = find_parent ( x ) )= = ( y = find_parent( y ) ) ) return ;

    if ( par [ y ] < par [ x ] )

    swap ( x , y );

    if ( par [ x ] == par [ y ] ) //depth increases by 1 if the depth of both groups are same

            par [ x ] --;

    par [ y ] = x;

}

Time Complexity: O ( log N ) ( if path compression is not used and O ( 1 ) if used )

Space Complexity: O ( N )

GeeksForGeeks Question:

Disjoint set (Union-Find)

Given an array A[] that stores all number from 1 to N (both inclusive and sorted) and K queries.

The task is to do the following operations on array elements :

1. UNION X Z : Perform union of X and Z i.e. parent of Z will become the parent of X.

2. FIND X: Find the parent of X and print it.

Input:
N = 5, K = 4
queries[] = {{find 4},
  {find 1},
  {unionSet 3 1},
  {find 3}}

Output:
4 1 1
Explanation:
1. The parent of 4 is 4. Hence the output is 4.
2. The parent of 1 is 1. Hence the output is 1.
3. After performing unionSet 3 1, parent of 3 becomes 1,
  since, parent of 1 is currently 1 itself.
4. The parent of 3 is now 1. Hence, the output is 1. You don't need to read input or print anything. Your task is to complete the functions- find() which takes an array A[] and an integer X as an input parameter and return the parent of X and the function unionSet() which takes an array A[] and two integers X and Z and performs the union of X and Z.
Expected Auxiliary Space: O(1)
1 <= N, K <= 100

Note: Initially all are the parent of themselves.

Expected Time Complexity: O(N)

int find(int A[],int X)

{   

        if(A[X]==X)return X;

       return A[X]= find(A,A[X]);

       

}

void unionSet(int A[],int X,int Z)

{

int a=find(A,X);

int b=find(A,Z);

A[a]=b;

}

Union-Find

This problem is to implement disjoint set union. There will be 2 incomplete functions namely union and find. You have to complete these functions. 

Union: Join two subsets into a single set.
isConnected: Determine which subset a particular element is in. This can be used for determining if two elements are in same subset.

Example 1:

Input:
N = 5
q = 4
Queries = 
Union(1,3)
isConnected(1,2)
Union(1,5)
isConnected(3,5)
Output:
0
1
Explanation: Initially all nodes 1 2 3 4 5
are not connected. 
After Union(1,3), node 1 and 3 will be
connected.
When we do isConnected(1,2),  as node 1
and 2 are not connected it will return 0.
After Union(1,5), node 1 and 5 will be
connected.
When we do isConnected(3,5),  as node
1 and 3 are connected, and node 1 and 5
are connected, hence 3 and 5 are
connected. Thus it will return 1.

Example 2:

Input:
N = 5
q = 4
Queries = 
Union(1,4)
Union(1,5)
isConnected(2,3)
Union(3,4)
Output: 0

Your Task:

You have to complete the function union_() which merges the node1 and node2. You will also have to complete the function isConnected() which will return whether the two nodes are connected.

Note: Both function will contain two arrays par[] and ranks1[] along with two nodes. Initially par[i] = i and rank1[i] = 1 

Expected Time Complexity: O(N + Q).
Expected Auxiliary Space: O(1).

Constraints: 
1 <= N <= 105
1<= Q <= 105
1 <= node1, node2 <= N

class Solution

{

    public:

    //Function to merge two nodes a and b.

    

    int find(int x,int par[]){

        if(x==par[x])return x;

        return par[x]=find(par[x],par);

    }

    

    void union_( int a, int b, int par[], int rank1[]) 

    {   

        int x=find(a,par);

        int y=find(b,par);

        if(x == y)return;

        if(rank1[x]<rank1[y])swap(x,y);

        if(rank1[x]==rank1[y])rank1[x]++;

        par[y]=x;

    }

    

    //Function to check whether 2 nodes are connected or not.

    bool isConnected(int x,int y, int par[], int rank1[])

    {

        if(find(x,par)==find(y,par))return true;

        return false;

    }

};

Tags:

dsu

disjoint set union

graph interview question

dsu data structure

disjoint set

union find algorithm

disjoint set example

disjoint set data structure

definition of disjoint set

graph coding questions

dsu

disjoint set union

graph interview question

dsu data structure

disjoint set

union find algorithm

disjoint set example

disjoint set data structure

definition of disjoint set

graph coding questions