Created
July 16, 2020 18:24
-
-
Save SuryaPratapK/3e58ebd6a3fe88f24b6bab14f1e03674 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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) |
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
what is need of again call find function in union_op becouse we already get absolute root of both element ?