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

Construct Binary Tree from preorder and inorder | Data Structure

Introduction: In this tutorial we are going to see how we can construct the binary tree from given preorder and inorder. Prerequisites: you should know about binary tree traversal and on paper you can draw binary tree from given preorder and inorder traversal. Inorder:left->root->right; Preorder:root->left->right; Problem Statement: we have given two arrays. one for preorder and another for inorder. by using these two array we have to built a binary tree. eg: preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] solution: Solution: We will follow recursive approach to solve this question.let's discuss how we can solve it. Trick: In the given preorder the very first element will be the root of the tree. then we will find root element in inorder also. and we know in inorder traversal we have left part then root and then right part of the tree. by using preorder we can get the root of the main tree and by using inorder and root we can get the left part and right part of the...
Post a Comment
Read more

DFS Application | Graph Problems | Max Area of Island

Introduction: In this tutorial, we are going to implement DFS  to solve another important problem. this is a good question for interview point of view. Problem Statement: Leetcode Input: [[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0, 1 ,0, 1 ,0,0], [0,1,0,0,1,1,0,0, 1 , 1 , 1 ,0,0], [0,0,0,0,0,0,0,0,0,0, 1 ,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]] Output: 6 Solution: So basically we are going to use DFS to solve this problem, and we will use a 2D vector to track the already visited element. let's see the code: Full Code: int helper(vector<vector<int>>& grid,int x, int y, vector<vector<int>>&visited){ if(x<0 || x>=grid.size() || y<0 || y>=grid[x].size()) return 0; if(grid[x][y]==0){ return 0; } if(visited[x][y]==1){ return 0; } visited[x][y]=1; // cout<<x...
Post a Comment
Read more