Disjiont Set Union-Find Data Structure | Code In C++

 Introduction: 

In this tutorial we are going to write full program of disjoint set union find advance data structure in c++. 

Problem Description:

Disjoint Set Union (DSU) is an advance data structure, which basically uses in graph algorithms to find

cycles.

Codes:

 Method1: Brute Force

#include<bits/stdc++.h>
using namespace std;
int find(int f,vector<int>&dsuf){
    if(dsuf[f]==-1)
        return f;
    return find(dsuf[f],dsuf);
}

void union_op(int from, int to, vector<int>& dsuf){
    dsuf[from]=to;
}
bool isCycle(vector<pair<int,int> >&edge_list, vector<int>&dsuf){
    for(int i=0;i<edge_list.size();i++){
        int parent1=find(edge_list[i].first,dsuf);
        int parent2=find(edge_list[i].second,dsuf);
        if(parent1==parent2)
            return true;
        union_op(parent1, parent2,dsuf);
    }
}

int main(){
    int v,e;
    cout<<"enetr the number of nodes and edges:";
    cin>>v>>e;
   
    vector<int>dsuf(v,-1);
   
    vector<pair<int,int> >edge_list;
    for(int i=0;i<e;i++){
        int x,y;
        cin>>x>>y;
        edge_list.push_back({x,y});
    }
   
    if(isCycle(edge_list,dsuf)){
        cout<<"cycle"<<endl;
    }
    else{
        cout<<"No cycle"<<endl;
    }
    return 0;
}

Method2: Rank Compression

#include<bits/stdc++.h>
using namespace std;
struct node{
    int parent;
    int rank;
};

int find(int f, vector<node>& dsuf){
    if(dsuf[f].parent==-1)
         return f;
    return dsuf[f].parent=find(dsuf[f].parent,dsuf);
}

void union_op(int from, int to, vector<node>&dsuf){
    if(dsuf[to].rank>dsuf[from].rank){
        dsuf[from].parent=to;
    }
    else if(dsuf[to].rank<dsuf[from].rank)
             dsuf[to].parent=from;
    else{
        dsuf[to].parent=from;
        dsuf[to].rank+=1;
    }
}
bool isCycle(vector<pair<int,int> >&edge_list,vector<node>&dsuf){
    for(int i=0;i<edge_list.size();i++){
        int parent1=find(edge_list[i].first,dsuf);
        int parent2=find(edge_list[i].second,dsuf);
        if(parent1==parent2)
            return true;
        union_op(parent1, parent2,dsuf);
    }
}
int main(){
    int v,e;
    cout<<"enetr the number of nodes and edges:";
    cin>>v>>e;
   
    vector<node>dsuf(v);
   
    for(int i=0;i<v;i++){
        dsuf[i].parent=-1;
        dsuf[i].rank=0;
    }
   
    vector<pair<int,int> >edge_list;
    for(int i=0;i<e;i++){
        int x,y;
        cin>>x>>y;
        edge_list.push_back({x,y});
    }
   
    if(isCycle(edge_list,dsuf)){
        cout<<"cycle"<<endl;
    }
    else{
        cout<<"No cycle"<<endl;
    }
    return 0;
}

Conclusion:

These are the two methods to implement DSU, in which Rank Compression technique is better than Brute Force technique.