C++14(g++5.4) 解法, 执行用时: 1677ms, 内存消耗: 101280K, 提交时间: 2020-05-13 11:19:32

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,m;
unordered_map<int,int>fazz;//初始化都为零 
int find(int v)
{
    if(fazz[v] == 0)
        return v;
    else
    {
        fazz[v]=find(fazz[v]);
        return fazz[v];
    }
}
/*void union(int x,int y)
{
	int m=find(x);
	int n=find(y);
	fazz[m]=n;
	return ;
}*/
int main()
{
	cin>>n;
	while(n--)
	{
		cin>>m;
		int flag=1;
		while(m--)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			if(flag==0)continue;
			int x,y;
			x=find(a),y=find(b); 
			if(c==1)
			{
				if(x!=y&&x!=a&&y!=b)flag=0;
				else fazz[x]=y;
			}
			else if(c==0)
			{
				if(x==y)flag=0;
			}
		}
		if(flag==0)printf("NO\n");
		else printf("YES\n");
		fazz.clear();
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 1934ms, 内存消耗: 144392K, 提交时间: 2023-05-13 20:24:35

#include<bits/stdc++.h>
using namespace std;
int t,n;		
unordered_map<int,int>p;
int find(int x){
	if(x!=p[x]) p[x]=find(p[x]);
	return p[x];
}
int main(){
	cin>>t;
	while(t--){
		p.clear();
		unordered_map<int,int>mp;
		scanf("%d",&n);
		int f=0;
		for(int i=0;i<n;i++){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
            if(f==1) continue;
            if(!p.count(a)) p[a]=a;
            if(!p.count(b)) p[b]=b;
			if(a>b) swap(a,b);
			if(c==1){
				if(mp[a]==b){
					f=1;
				}else p[find(a)]=p[find(b)];
			}else{
				if(p[find(a)]==p[find(b)]){
					f=1;
				}else mp[a]=b;
			}
		}if(f==1){
			printf("NO\n");
		}else{
			printf("YES\n");
		}
	}
	return 0;
}

pypy3 解法, 执行用时: 3094ms, 内存消耗: 175364K, 提交时间: 2023-04-02 16:53:45

def merge(x: int):
    global mp
    if mp.__contains__(x) == False:
        mp[x] = x
        return x
    while x != mp[x]:
        x, mp[x] = mp[x], mp[mp[x]]
    return x


mp = dict()
t = int(input())
for i in range(t):
    n, flag = int(input()), False
    for j in range(n):
        a, b, c = map(int, input().split())
        if flag == True:
            continue
        x, y = merge(a), merge(b)
        if c == False:
            flag = (x == y)
        elif x < y:
            mp[b] = x
        elif x > y:
            mp[a] = y
    if flag == True:
        print("NO")
    else:
        print("YES")

C++ 解法, 执行用时: 1201ms, 内存消耗: 81620K, 提交时间: 2021-06-17 20:25:46

#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;
unordered_map<int,int> f;
int find(int v){
	return f[v]==0?v:find(f[v]);
}
void merge(int u,int v){
	int t1=find(u),t2=find(v);
	f[t1]=t2;
}
int main(){
	int T,n,a,b,c;
	scanf("%d",&T);
	while(T--){
		bool flag=true;
		scanf("%d",&n);
		while(n--){
			scanf("%d%d%d",&a,&b,&c);
			if(!flag) continue;
			int x=find(a),y=find(b);
			if(c==1){
				if(x!=a&&y!=b&&x!=y) flag=false;
				else f[x]=y;
			}
			else if(x==y) flag=false;
		}
		printf("%s\n",flag?"YES":"NO");
		f.clear();
	}
	return 0;
}