Facebook
From dsu, 8 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 354
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<pair<int,int>> adj;
  4. vector<int> parent;
  5. vector<int> Rank;
  6. int n=4;
  7. void addEdge(int i, int j)
  8. {
  9.     adj.push_back(make_pair(i,j));
  10. }
  11. void makeSet()
  12. {
  13.     parent.resize(n);
  14.     Rank.resize(n);
  15.     for(int i=0; i<n; i++)
  16.     {
  17.         parent[i]=-1;
  18.         Rank[i]=1;
  19.     }
  20. }
  21. int find(int i)
  22. {
  23.     if(parent[i]==-1) return i;
  24.     else return parent[i]=find(parent[i]);
  25. }
  26. void Union(int i, int j)
  27. {
  28.     int s1 = find(i);
  29.     int s2 = find(j);
  30.     if(s1!=s2)
  31.     {
  32.         if(Rank[s1]<Rank[s2])
  33.         {
  34.             parent[s1]=s2;
  35.             Rank[s2]+=Rank[s1];
  36.         }
  37.         else
  38.         {
  39.             parent[s2]=s1;
  40.             Rank[s1]+=Rank[s2];
  41.         }
  42.     }
  43. }
  44. bool detectCycle()
  45. {
  46.     makeSet();
  47.     for(auto edge:adj)
  48.     {
  49.         int i=edge.first;
  50.         int j=edge.second;
  51.         int s1=find(i);
  52.         int s2=find(j);
  53.         if(s1!=s2) Union(i,j);
  54.         else {
  55.             cout<<"Cycle detected"<<endl;
  56.             cout<<"Their parent are "<<s1<<" "<<s2<<endl;
  57.             return true;
  58.         }
  59.     }
  60.     return false;
  61. }
  62. int main()
  63. {
  64.     addEdge(0,1);
  65.  addEdge(1,2);
  66.  addEdge(2,3);
  67.  addEdge(3,0);
  68.     cout<<detectCycle()<<endl;
  69.    // for(auto i:Rank) cout<<i<<" ";
  70.     for(int i=0; i<n; i++)
  71.     {
  72.         if(parent[i]==-1) cout<<"Representative "<<i<<" Total size "<<Rank[i]<<endl;
  73.     }
  74.     cout<<endl;
  75.     cout<<count(parent.begin(), parent.end(), -1)<<endl;
  76. }