链接： https://ac.nowcoder.com/acm/contest/893/G
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
Special Judge, 64bit IO Format: %lld
题目描述
有n个人在玩一个身份扮演的游戏。
把这n个人编号为1,2,3...n。
其中每个人会扮演下面两种身份中的一种:
Truthman:当某个人扮演Truthman时，这个人只会说真话。
Fakeman:当某个人扮演Fakeman时，这个人只会说假话。
这n个人是互相知道身份的，但是Casya作为一个旁观者不知道任何一个人的身份。
为了让Casya有可能推断这些人的身份，这n个人说了m句话。
每句话的内容只包含某人对某人身份的一条描述，且被Casya记录为以下形式:
u,v,0 -- u认为v是一个Fakeman;
u,v,1 -- u认为v是一个Truthman;
当然这些话不一定都是真话，这取决于说话的人的身份。
但是可以肯定的是身份只有两种，也就是说某个人不是Truthman就是Fakeman。

Casya想知道不违反上面的条件和记录最少有多少个Fakeman，除此之外他还想得到一组在此情况下的一组合理的解—即所有人的身份。或者确定记录本来就是矛盾的所以没有任何符合条件的解。
输入描述:

第一行一个数字T(1≤T≤30)

--样例个数。
其中每个样例:
第一行两个数字n,m(1≤n≤10^5,0≤m≤10^5)。
然后m行,每一行包含三个整数u,v,w(1≤u,v≤n,w={0,1})
保证所有样例中∑n不超过2×10^6。
保证所有样例中∑m不超过2×10^6

。

输出描述:

每个样例输出一行。
如果存在合理的解，输出一个长度为n的字符串，且只包含’0’或’1’。
其中第i个字符为’0’表示i是一个Fakeman，为’1’表示i是一个Truthman。并使得Fakeman的数量最少。如果有多个解符合要求，输出任意一个即可。

如果不存在任何合理的解，输出-1。

示例1
输入
复制

2  
5 4  
1 2 1  
2 3 0  
2 4 0  
1 5 0  
3 3  
1 2 1  
1 3 0  
2 3 1

输出
复制

00111
-1

w是1的话，u，v一定同类

w是0的话，u，v一定异类

1~n代表真

n+1~2n代表假

https://blog.csdn.net/henuyh/article/details/89951847

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int pre[N<<1],num[N<<1],vis[N<<1],ans[N];
int n,m;
int find(int x){
	return x==pre[x]?pre[x]:pre[x]=find(pre[x]);
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		pre[fx]=fy;
		num[fy]+=num[fx];//人数合并
	}
}
void solve(){
	for(int i=1;i<=n;i++){
		int fx=find(i);
		int fy=find(i+n);
		if(fx==fy){
			printf("-1\n");
			return ;
		}
		if(vis[fx]==0){//集合是否已经确定
			if(num[fx]>num[fy]){
				vis[fx]=1;
				vis[fy]=-1;
			}
			else{
				vis[fx]=-1;
				vis[fy]=1;
			}
		}
		ans[i]=(vis[fx]==1);
	}
	for(int i=1;i<=n;i++) printf("%d",ans[i]);
	printf("\n");
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=2*n;i++){
			pre[i]=i;
			num[i]=(i<=n);
			vis[i]=0;
		}
		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			if(w==1){
				merge(u,v);
				merge(u+n,v+n);
			}
			else{
				merge(u,v+n);
				merge(u+n,v);
			}
		}
		solve();
	}	
	return 0;
}