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. }