90分求助!#2 TLE
查看原帖
90分求助!#2 TLE
737088
WUYUEZE楼主2024/10/8 10:01
#include<bits/stdc++.h>
using namespace std;
int a,b;
struct node{
    int x,y;
    bool z;
};
node n[100010];
bool cmp(node a,node b){
    return a.z>b.z;
}
int p[100010];
int f(int x){
    int y=x;
    while(p[x]!=x){
        x=p[x];
    }
    while(p[y]!=y){
        int z=p[y];
        p[y]=x;
        y=z;
    }
    return x;
}
int main(){
    scanf("%d",&a);
    while(a--){
        scanf("%d",&b);
        set<int> m;
        map<int,int> o;
        for(int i=0;i<b;i++){
            scanf("%d%d%d",&n[i].x,&n[i].y,&n[i].z);
            m.insert(n[i].x);
            m.insert(n[i].y);
        }
        int w=1;
        while(m.size()){
        	o[*m.begin()]=w;
        	p[w]=w;
        	w++;
        	m.erase(m.begin());
		}
        sort(n+0,n+b,cmp);
        bool ky=1;
        for(int i=0;i<b;i++){
        	n[i].x=o[n[i].x];
        	n[i].y=o[n[i].y];
            if(f(n[i].x)==f(n[i].y)){
                if(!n[i].z){
                    ky=0;
                    break;
                }
            }
            else{
                if(n[i].z){
                    n[i].x=f(n[i].x);
                    n[i].y=f(n[i].y);
                    if(n[i].x>n[i].y){
                        swap(n[i].x,n[i].y);
                    }
                    p[n[i].y]=n[i].x;
                }
            }
        }
        if(ky){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}
2024/10/8 10:01
加载中...