鏈接：https://ac.nowcoder.com/acm/problem/25579
來源：牛客網

時間限制：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≤1e5 )。
然后m行,每一行包含三個整數u,v,w(1≤u,v≤n,w={0,1})
保證所有樣例中\sum n∑n不超過2×1e6 。
保證所有樣例中\sum m∑m不超過2×1e6。
輸出描述:
每個樣例輸出一行。
如果存在合理的解，輸出一個長度為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

/*
當然這些話不一定都是真話，這取決于說話的人的身份。
當u說v是truthman，（u，v，w = 1）時，u，v一定是同一陣營的，要么都truth，要么都fake。
而u說v是fakeman，（u，v, w = 0）時，u，v一定是不同陣營的。
此時我們需要劃分出兩個集合，一個truthman，另一個fakeman，
這兩個集合中哪個是truthman集合取決于哪個集合人數更多，因為這兩個集合一定互斥，
題目要求最少的fakeman，反之更多的truthman。
一個人的身份開始不確定，本題處理方式：原編號+n作為另一種可能身份的編號。
本題有可能某些人是沒有被描述到的，由于初始化集合操作，
最初每個人只屬于一個小集合，此時到最后可以統一處理，
哪個集合人數多就歸到哪個集合去。
-1的情況：
查一個人的根，當一個人的根有兩種身份的時候，直接輸出-1即可
*/
Ac_code:

#include <stdio.h> const int MAXN = 1e5+5; int pre[MAXN<<1]; int cnt[MAXN<<1]; int vis[MAXN<<1]; int n,m; void init() {for(int i = 1; i <= (n<<1); i++){vis[i] = 0;pre[i] = i;cnt[i] = (i<=n);} } int myFind(int x) {return x == pre[x] ? x : pre[x] = myFind(pre[x]); } void myUnion(int x,int y) {int fx = myFind(x);int fy = myFind(y);if(fx != fy){pre[fx] = fy;cnt[fy] += cnt[fx];} } void solve() {for(int i = 1; i <= n; i++){int x = myFind(i);int y = myFind(i+n);if(x == y){puts("-1");return;}if(vis[x] == 0)//集合未確定{//哪個集合人數多就歸為truthman，vis標記為1if(cnt[x] > cnt[y]){vis[x] = 1;vis[y] = -1;}else{vis[y] = 1;vis[x] = -1;}}}for(int i = 1; i <= n; i++){if(vis[myFind(i)] == 1)printf("1");elseprintf("0");}puts("");return; } int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);init();int u,v,w;for(int i = 0; i < m; i++){scanf("%d%d%d",&u,&v,&w);if(w){//兩個人是相同身份myUnion(u,v);myUnion(u+n,v+n);}else{//兩個人是不同身份myUnion(u,v+n);myUnion(u+n,v);}}solve();}return 0; }

總結

以上是生活随笔為你收集整理的2019年湘潭大学程序设计竞赛（重现赛）F.Truthman or Fakeman(并查集)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。