fork download 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. // Path option optimization : Tối ưu nén đường
  5. // Tối ưu gộp kích thước
  6. int n ;
  7. const int maxn = 1005;
  8. int parent[1000001],sz[maxn];
  9.  
  10. void ktao(){
  11.     cin >> n ;
  12.     for(int i = 1 ; i <= n ; i++){
  13.         parent[i] = i;
  14.         sz[i] = 1;
  15.     }
  16. }
  17.  
  18. int Find(int u){
  19.     while(u != parent[u]){
  20.         u = parent[u];
  21.     }
  22.     return u;
  23. }
  24. /*
  25. int Find(int u){
  26.     if(u == parent[u]) return u ;
  27.     else return parent[u] = Find(parent[u]);
  28. }
  29. */
  30.  
  31. bool Union(int u,int v){
  32.     u = Find(u);
  33.     v = Find(v);
  34.     if(u == v){
  35.         return false;
  36.     }
  37.     else{
  38.         if(u < v) parent[v] = u;
  39.         else parent[u] = v;
  40.         return true;
  41.     }
  42. }
  43. /*bool Union(int u,int v){
  44.     u = Find(u);
  45.     v = Find(v);
  46.     if(u == v) return false;
  47.     if(sz[u] < sz[v]){
  48.         swap(u,v);
  49.     }
  50.     sz[u] += sz[v];
  51.     parent[v] = u;
  52.     return true;
  53. }*/
  54. int main(){
  55.     ktao();
  56.     cout << Find(5) << endl;
  57.     cout << Union(5,6) << " " << Find(6);
  58. }
  59.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin 
Standard input is empty
stdout 
0
0 0
https://ideone.com/Jh02xN
DISJOINT SET UNION
language:
C++ (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!