Skip to content

Instantly share code, notes, and snippets.

@SuryaPratapK
Created July 16, 2020 18:24
Show Gist options
  • Select an option

  • Save SuryaPratapK/3e58ebd6a3fe88f24b6bab14f1e03674 to your computer and use it in GitHub Desktop.

Select an option

Save SuryaPratapK/3e58ebd6a3fe88f24b6bab14f1e03674 to your computer and use it in GitHub Desktop.
#include<bits/stdc++.h>
using namespace std;
vector<int> dsuf;
//FIND operation
int find(int v)
{
if(dsuf[v]==-1)
return v;
return find(dsuf[v]);
}
void union_op(int fromP,int toP)
{
fromP = find(fromP);
toP = find(toP);
dsuf[fromP] = toP;
}
bool isCyclic(vector<pair<int,int>>& edge_List)
{
for(auto p: edge_List)
{
int fromP = find(p.first); //FIND absolute parent of subset
int toP = find(p.second);
if(fromP == toP)
return true;
//UNION operation
union_op(fromP,toP); //UNION of 2 sets
}
return false;
}
int main()
{
int E; //No of edges
int V; //No of vertices (0 to V-1)
cin>>E>>V;
dsuf.resize(V,-1); //Mark all vertices as separate subsets with only 1 element
vector<pair<int,int>> edge_List; //Adjacency list
for(int i=0;i<E;++i)
{
int from,to;
cin>>from>>to;
edge_List.push_back({from,to});
}
if(isCyclic(edge_List))
cout<<"TRUE\n";
else
cout<<"FALSE\n";
return 0;
}
//TIME COMPLEXITY: O(E.V)
@BeingCoder786
Copy link

what is need of again call find function in union_op becouse we already get absolute root of both element ?

@krishangopal123
Copy link

what is need of again call find function in union_op becouse we already get absolute root of both element ?

@saksham-kapoor
Copy link

what is need of again call find function in union_op becouse we already get absolute root of both element ?

There is no need! Here, he has written that to show the general implementation of Union function in disjoint sets.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment