1 条题解

  • -1
    @ 2022-8-11 19:09:20
    /*
    ID: Keqi Zhao
    TASK: test
    LANG: C++                 
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #define Maxn 1000010
    using namespace std;
    int n, bt, ct, T, b[Maxn * 2], c[Maxn * 2], fa[Maxn * 2];
    struct node{
    	int x, y, z;
    }a[Maxn];
    int find (int x){
    	if(fa[x] == x)
    		return x;
    	return fa[x] = find(fa[x]);
    }
    void merge(int x, int y){
    	x = find(x);
    	y = find(y);
    	if(x != y)
    		fa[x] = y;
    }
    int main() {
    	cin >> T;
    	while(T--){
    		cin >> n;
    		bt = 0, ct = 0;
    		for(int i = 1; i <= n; i ++){
    			cin >> a[i].x >> a[i].y >> a[i].z;
    			b[++bt] = a[i].x;
    			b[++bt] = a[i].y;
    		}
    		sort(b + 1, b  + bt + 1);
    		for(int i = 1; i <= bt; i++)
    			if(b[i] != b[i - 1])
    				c[++ct] = b[i];
    		for(int i = 1; i <= bt; i++){
    			a[i].x = lower_bound(c + 1, c + ct + 1, a[i].x) - c;
    			a[i].y = lower_bound(c + 1, c + ct + 1, a[i].y) - c;
    		}
    		for(int i = 1; i <= ct; i++)
    			fa[i] = i;
    		for(int i = 1; i <= n; i++)
    			if(a[i].z)
    				merge(a[i].x , a[i].y);
    		bool flag = true;
    		for(int i = 1; i <= n; i++)
    			if(!a[i].z)
    				if(find(a[i].x) == find(a[i].y)){
    					flag = false;
    					break;
    				}
    		cout << (flag  ? "YES" : "NO") << endl;
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    4195
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    32
    已通过
    10
    上传者