P1955 90分 #2RE 求调
查看原帖
P1955 90分 #2RE 求调
1288620
zgy88888888楼主2025/1/27 12:31
#include <bits/stdc++.h>
using namespace std;
int t,n,t1,t2,e,c,f[400010];
int fqq(int x){
    if (f[x]==x){
        return x;
    }
    f[x]=fqq(f[x]);
    return f[x];
}
struct student{
    int a,b,p;
} x[400010];
bool cmp(student a,student b){
    return a.p>b.p;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for (int i = 0; i < 400010; i++)
        {
            f[i]=i;
        }
        map<int,int> a;
        for (int i = 0; i < n; i++)
        {
            cin>>t1>>t2>>e;
            if (!a[t1]){
                a[t1]=c++;
            }
            if (!a[t2]){
                a[t2]=c++;
            }
            x[i]={t1,t2,e};
        }
        sort(x,x+n,cmp);
        bool l=1;
        for (int i = 0; i < n; i++)
        {
            if(x[i].p){
                f[fqq(x[i].a)]=fqq(x[i].b);
            }
            else{
                if(fqq(x[i].a)==fqq(x[i].b)){
                    cout<<"NO"<<'\n';
                    l=0;
                    break;
                }
            }
        }
        if(l){
            cout<<"YES"<<'\n';
        }
    }
    return 0;
}

#2RE 90分

2025/1/27 12:31
加载中...