Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Linked List Data Structure | Add Two Number Explanation

Introduction: In this tutorial, we are going to solve a very famous problem on Linked List. It is also an important question for coding interview. so let's see the problem and understand it in detail. Problem Statement: There are two numbers and each digit of number is represented by a node of linked list.and we have to add these two numbers, which is given in the form of linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 eg: num1 = 2354;       num2 = 875; see the image below: Solution: Now let's solve it. In this problem there may be three possibilities. First: Number of Nodes in the first linked list is greater than second linked list. Second: Number of Nodes in first linked list is less than second list. Third: Number of Nodes in the both linked list is equal. Here number of nodes means number of digits in both number. Another thing we have to keep in mind is that if we add two digits then there may be possibility of gen...
Post a Comment
Read more

Integrating Frontend to Backend | MERN stack(100% working)

How to Integrate frontend to backend in MERN stack? For integrating the frontend to backend just do two things. Step1: Go and install cors on both side (front end as well as backend)              To install cors simply open the folder into terminal and type npm install cors--save. step 2: just go to your front end section(react app) open package.json file.                 and just add one line into package.json file.           "proxy":"http://localhost:4000" here i am using 4000, so what is 4000 ?. this is the port  on which our backend is listening. so it may be possible that u may have other port number on which your server is listening. so put yours port number on which your backend server is listening. and this proxy thing we have to add in frontend part not in backend part. Now it may be possible that you want to know ...
Post a Comment
Read more