30pt求调,悬赏关注
查看原帖
30pt求调,悬赏关注
456675
a_sad_soul楼主2023/9/23 21:26
#include<bits/stdc++.h>
#define MAXN 4000005
using namespace std;
int fa[MAXN];
int find(int x)
{
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int a,int b){
    if(find(a)!=find(b))
        fa[find(a)]=find(b);
}
int t;
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x;
}
struct node{
    long long a,b,e;
}num[MAXN];
int main()
{
    freopen("P1955_2.in","r",stdin);
    int t=read();
    while(t--)
    {
        for(int i=1;i<MAXN;++i)
            fa[i]=i;
        int n=read();
        vector<long long>sor;
        unordered_map<long long ,int>mp;
        for(int i=1;i<=n;++i)
        {
            num[i].a=read(),num[i].b=read(),num[i].e=read();
            sor.push_back(num[i].a),sor.push_back(num[i].b);
        }
        sort(sor.begin(),sor.end());
        int k=unique(sor.begin(),sor.end())-sor.begin();
        for(int i=0;i<k;++i)
            mp[sor[i]]=i+1;
        bool ans=0;
       // cout<<k<<endl;
        for(int i=1;i<=n;++i)
        {
            if(num[i].e)
                if(find(mp[num[i].a]+n+n)==find(mp[num[i].b]+n+n)&&num[i].a!=num[i].b)
                   {ans=1;break;}
                else 
                    merge(mp[num[i].a],mp[num[i].b]);
            else  
                if(find(mp[num[i].a])==find(mp[num[i].b]))
                    {ans=1;break;}
                else
                    merge(mp[num[i].a]+n+n,mp[num[i].b]+n+n);
        }
        if(ans)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}
2023/9/23 21:26
加载中...