2 条题解

  • 0
    @ 2021-01-28 11:33:10
    #include<bits/stdc++.h>
    #define MAXN 100005
    using namespace std;
    
    int n,fa[MAXN],u[MAXN],v[MAXN],t[MAXN];
    
    int getfa(int Node){
        if(Node==fa[Node])return Node;
        else return fa[Node]=getfa(fa[Node]);
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin>>n;
        for(int i=1;i<=n;++i){
            fa[i]=i;
        }
        for(int i=1;i<=n;++i){
            cin>>u[i]>>v[i]>>t[i];
            if(t[i]==1){
                int fau,fav;
                fau=getfa(u[i]);
                fav=getfa(v[i]);
                if(fav!=fau){
                    fa[fav]=fau;
                }
            }
        }
        int fl=1;
        for(int i=1;i<=n;++i){
            int fav,fau;
            fav=getfa(v[i]);
            fau=getfa(u[i]);
            if(t[i]==0&&fav==fau)fl=0;
            if(t[i]==1&&fav!=fau)fl=0;
        }
        if(fl)puts("Yes");
        else puts("No");
        return 0;
    }
    
  • 0
    @ 2021-01-27 22:09:28
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<stdio.h>
    using namespace std;
    const int N=200005;
    pair<int,int>unequal[N];
    int t,num,sum,x[N],y[N],tof[N],father[N],d[N];
    int find(int x)
    {
        if(father[x]==x)
        {
         return x;   
        }  
        else
        {
         return father[x]=find(father[x]);
        }
    }
    void getunion(int x,int y)
    {
        x=find(x),y=find(y);
        if(x!=y)  
        {
            father[x]=y;
    }
    }
    void dig(int sum)
    {
        sort(d+1,d+sum+1);
        int m=unique(d+1,d+sum+1)-d-1;
        for(int i=1;i<=t;++i)
        {
            x[i]=lower_bound(d+1,d+m+1,x[i])-d;
            y[i]=lower_bound(d+1,d+m+1,y[i])-d;
        }
    }
    int main()
    {
        int i,t,a,b;
        scanf("%d",&t);
             num=0,sum=0;
              for(i=1;i<=t;i++)
              {
                father[i]=i;  
              }
               for(i=1;i<=t;++i)
            {
                scanf("%d%d%d",&x[i],&y[i],&tof[i]);
                d[++sum]=x[i];
                d[++sum]=y[i];
            }
            dig(sum);
            for(i=1;i<=t;++i)
            {
                if(tof[i]==1)  
                {
                    getunion(x[i],y[i]);
                }
                else 
                {
                    unequal[++num]=make_pair(x[i],y[i]);
                    } 
            }
            for(i=1;i<=num;++i)
           {
                a=find(unequal[i].first);
                 b=find(unequal[i].second);
                if(a==b){
                    printf("No");
                    goto end;
                    }
           }
          printf("Yes");
          end:;
    }
    
  • 1

信息

ID
1004
难度
9
分类
并查集 点击显示
标签
(无)
递交数
6
已通过
4
通过率
67%
被复制
1
上传者