NCD 2019 H. Mr. Hamra and his quantum particles

• 题意:给你n个数,有m次操作,每次使得两个数相连接,询问q次,问某两个数是否连接在一起.

• 题解:这其实是一道并查集的裸题,这里就不再多说了,写个路径压缩的find函数即可.

• 代码:

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  #include <cmath>
  #include <algorithm>
  #include <stack>
  #include <queue>
  #include <vector>
  #include <map>
  #include <set>
  #include <unordered_set>
  #include <unordered_map>
  #define ll long long
  #define fi first
  #define se second
  #define pb push_back
  #define me memset
  const int N = 1e6 + 10;
  const int mod = 1e9 + 7;
  using namespace std;
  typedef pair<int,int> PII;
  typedef pair<long,long> PLL;
  
  int t;
  int u,v,x,y;
  int n,m,q;
  int p[N];
  int find(int x){          //dsu
      if(p[x]!=x) p[x]=find(p[x]);
      return p[x];
  }
  
  int main() {
      ios::sync_with_stdio(false);
      cin>>t;
       while(t--){
           cin>>n>>m>>q;
           for(int i=1;i<=n;++i) p[i]=i;
            while(m--){
              cin>>u>>v;
              p[find(u)]=find(v);
            }
            while(q--){
                cin>>x>>y;
                 if(find(x)==find(y)) printf("1");
                 else printf("0");
            }
            puts("");
       }
      return 0;
  }
  

NCD 2019 H. Mr. Hamra and his quantum particles

原文：https://www.cnblogs.com/lr599909928/p/12830396.html