Advertisement
Josif_tepe

Untitled

Jul 15th, 2023
777
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. const int maxn=1e6+10;
  6. int idx[maxn];
  7. int s[maxn];
  8.  
  9. int find_root( int x)
  10. {
  11.     int t = x;
  12.     while(idx[t]!=t)
  13.     {
  14.         idx[t]=idx[idx[t]];
  15.         t=idx[t];
  16.     }
  17.     return t;
  18. }
  19.  
  20.  
  21. void u2e( int  i, int  j)
  22. {
  23.     int idx_i=find_root(i);
  24.     int idx_j=find_root(j);
  25.     if(idx_i!=idx_j)
  26.     {
  27.         if(s[idx_i] > s[idx_j])
  28.         {
  29.             s[idx_i]+=s[idx_j];
  30.             idx[idx_j]=idx[idx_i];
  31.         }
  32.         else
  33.         {
  34.             s[idx_j]+=s[idx_i];
  35.             idx[idx_i]=idx[idx_j];
  36.         }
  37.     }
  38. }
  39.  
  40. int main()
  41. {
  42.     ios_base::sync_with_stdio(false);
  43.    
  44.     int n;
  45.     int q;
  46.     cin>>n>>q;
  47.     for(int i=0;i<n;i++)
  48.     {
  49.         idx[i]=i;
  50.         s[i]=1;
  51.     }
  52.     while(q--)
  53.     {
  54.         char c;
  55.         int a,b;
  56.         cin>>c>>a>>b;
  57.         if(c=='=')
  58.         {
  59.             u2e(a,b);
  60.         }
  61.         else
  62.         {
  63.             if(find_root(a) == find_root(b))
  64.             {
  65.                 printf("yes\n");
  66.             }
  67.             else
  68.             {
  69.                 printf("no\n");
  70.             }
  71.         }
  72.     }
  73.     return 0;
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement