并查集相关

全部评论 2

• 

  hjh-已被收容

  删除

  简化版

  #include<bits/stdc++.h>
  using namespace std;
  const int N=2*1e5+100;
  int n,m;
  int fa[N];
  int siz[N];
  void pre(){
      for(int i=1;i<=n;++i){
          fa[i]=i;
          siz[i]=1;
      }
  }
  int find(int x) {
      //自己是根节点
      if (fa[x] == x) return x;
      //让自己的父亲是根节点
      fa[x] = find(fa[x]);
      //返回根节点
      return fa[x];
  }
  int size(int x) {
      return siz[find(x)];
  }
  
  void merge(int u, int v) {
      //找到自己的根节点
      u = find(u), v = find(v);
      if (u == v)return;
      if (size(u) < size(v))swap(u, v);
      // 合并两个树的w大小
      siz[u] += siz[v];
      // 合并
      fa[v] = fa[u];
  }
  
      
  
   bool same(int u, int v) {
      return find(u) == find(v);
  }
  
  int main(){
      cin>>n>>m;
      pre();
      while(m--){
          int z,x,y;
          cin>>z>>x>>y;
          if(z==1){
              merge(x,y);
          }
          else{
              if(same(x,y))cout<<"Y";
              else cout<<"N";
              cout<<endl;
              
          }
      }
  }
  

  2025-08-06 来自 浙江

  0
• 

  hjh-已被收容

  删除

  

  #include<bits/stdc++.h>
  using namespace std;
  const int N=1e6+100;
  int n,m;
  int fa[N];
  int siz[N];
  struct node{
      int x,y,t;
  }Num[N];
  bool cpp(node a,node b){
     return a.t<b.t;
  }
  
  void pre(int j){
      for(int i=1;i<=j;++i){
          fa[i]=i;
          siz[i]=1;
      }
  }
  int find(int x) {
      //自己是根节点
      if (fa[x] == x) return x;
      //让自己的父亲是根节点
      fa[x] = find(fa[x]);
      //返回根节点
      return fa[x];
  }
  int size(int x) {
      return siz[find(x)];
  }
  
  void merge(int u, int v) {
      //找到自己的根节点
      u = find(u), v = find(v);
      if (u == v)return;
      if (size(u) < size(v))swap(u, v);
      // 合并两个树的w大小
      siz[u] += siz[v];
      // 合并
      fa[v] = fa[u];
  }
  
      
  
   bool same(int u, int v) {
      return find(u) == find(v);
  }
  
  void solve(){
      cin>>n;
  
      map <int,int> mp;
      int id=0;
      vector <vector<pair<int,int> > >ed(2);
      for(int i=1;i<=n;++i){
          int u,v,op;
          cin>>u>>v>>op;
          if(!mp[u])mp[u]=++id;
          if(!mp[v])mp[v]=++id;
          u=mp[u],v=mp[v];
          ed[op].push_back({u,v});
      }
  
      pre(id+10);
      for(auto i:ed[1]){
          merge(i.first,i.second);
      }
      for(auto i:ed[0]){
          if(same(i.first,i.second)){
              cout<<"NO"<<endl;
              return;
          }
      }
      cout<<"YES"<<endl;
      return;
  }
  int main(){
      int t;
      cin>>t;
      while(t--){
          solve();
      }
  }
  

  2025-08-06 来自 浙江

  0