2019年湘潭大学程序设计竞赛-G Truthman or Fakeman

题目：有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，除此之外他还想得到一组在此情况下的一组合理的解—即所有人的身份。或者确定记录本来就是矛盾的所以没有任何符合条件的解。

分析：如果A说B是Truthman 那么A和B是同一个团体，如果A说B是Fakeman，那么A和B是不同的两个团体，这两个条件只需在图上建立一个权值标记就行了，对于一个联通块，确定一个点的性质之后，整个联通块的每个点的性质就都确定了。只要将较大的那个定义为Truthman就好了，用dfs遍历连通块，如果一开始设为Truthman的团体较小那就再dfs一遍取反。

补充：这题也可以用种类并查集来做，可以参考https://blog.csdn.net/weixin_43849505/article/details/90082395

https://blog.csdn.net/qq_42936517/article/details/90021825

代码：

#

#include <bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;
int t,n,m,vs[N],a[N],flag,s1,s2;
struct nd{
    int v,w;
};
vector<nd> e[N];
void dfs(int u) {
    vs[u]=1;
    if(a[u]) s1++;
    else s2++;
    for(int i=0;i<e[u].size();i++) {
        int v=e[u][i].v,w=e[u][i].w;
        if(!vs[v]) {
            if(w) a[v]=a[u];
            else a[v]=a[u]^1;
            dfs(v);
        }else if((w&&a[u]!=a[v])||(w==0&&a[u]==a[v])) flag=1;
    }
}
void dfs2(int u) {
    vs[u]=2,a[u]^=1;
    for(int i=0;i<e[u].size();i++) {
        int v=e[u][i].v;
        if(vs[v]==1) {
            dfs2(v);
        }
    }
}
int main () {
    while (~scanf("%d",&t)) {
        while(t--) {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) e[i].clear();
            memset(vs,0,sizeof(vs));
            memset(a,0,sizeof(a));
            flag=0;
            for(int i=1,u,v,w;i<=m;i++) {
                scanf("%d%d%d",&u,&v,&w);
                if(w) e[u].push_back({v,1}),e[v].push_back({u,1});
                else e[u].push_back({v,0}),e[v].push_back({u,0});
            }
            for(int i=1;i<=n;i++) {
                if(!vs[i]) {
                    a[i]=1,s1=s2=0;
                    dfs(i);
                    if(s1<s2) dfs2(i);
                }
            }
            if(flag) printf("-1\n");
            else {
                for(int i=1;i<=n;i++)
                    printf("%d",a[i]==1);
                printf("\n");
            }
        }
    }
    return 0;
}