codeforces 747 div2 D The Number of Imposters 题解

题目大意

有 $n$ 个人，每个人的身份都是以下两个中的一个：imposter，crewmate。

一共有 $m$ 个陈述，形如：$x$ $y$ imposter/crewmate，表示，$x$ 说 $y$ 的身份是 imposter/crewmate。

注意，imposter 只会说谎，crewmate 只会说实话。

求：imposter 最多可能有多少个。

思路

像这种划分阵营的题，我们无需知道每个人属于哪个阵营，只需知道哪些人属于同一个阵营。

对于上面的两种陈述：

1. $x$ $y$ imposter：那么显然 $x$ 和 $y$ 属于不同的阵营
2. $x$ $y$ crewmate：那么 $x$ 和 $y$ 属于相同阵营

那么我们用 $0$ 和 $1$ 代表两个不同阵营（仅用于表示哪些人在同一阵营），用来表示点的权值。

我们建一个图，当出现情况1时，我们从 $x$ 向 $y$ 连一条权值为 $1$ 的双向边，出现情况2时，我们 $x$ 向 $y$ 连一条权值为 $0$ 的双向边。

那么之后我们可以遍历整张图，通过边权值与当前点的权值，通过异或边权，来判断下一个点的权值。

即，通过遍历，来判断能否构造出满足题意的阵营分配。

比如当前点权值为 $0$，通过一个边权为 $1$ 的边，连向一个还未访问的点，那么新的点的权值就是 $0 \oplus 1 = 1$（属于两个不同阵营）。

当然如果这个点被访问过了，我们需要看一下它的权值是否是 $0 \oplus 1 = 1$，如果不是，那么显然就出现矛盾了，输出 $-1$。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int maxN = 2e5 + 7, maxM = 5e5 + 7;

int T, n, m, id[maxN], sum[3];
bool succ;

struct Edge {
    Edge(int _to, int _identity) {
        to = _to;
        identity = _identity;
    }
    int to, identity;
};

vector<Edge> e[maxM];

inline void init()
{
    for(int i = 1; i <= (n + m); ++i)
        e[i].clear();
    memset(id, -1, sizeof(id));
}

void dfs(int now)
{
    sum[id[now]]++;
    for(int i = 0; i < e[now].size(); ++i) {
        if(id[e[now][i].to] == -1) {
            id[e[now][i].to] = id[now] ^ e[now][i].identity;
            dfs(e[now][i].to);
        }
        else if(id[e[now][i].to] != (id[now] ^ e[now][i].identity)) {
            succ = false;
        }
    }
}

inline void work()
{
    init();
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        char s[11]; int x, y;
        scanf("%d%d%s", &x, &y, s);
        if(s[0] == 'c') {
            e[x].push_back(Edge(y, 0));
            e[y].push_back(Edge(x, 0));
        }
        else {
            e[x].push_back(Edge(y, 1));
            e[y].push_back(Edge(x, 1));
        }
    }
    int ans = 0; succ = true;
    for(int i = 1; i <= n; ++i) {
        if(id[i] == -1) {
            sum[0] = sum[1] = 0;
            id[i] = 0;
            dfs(i);
            ans += max(sum[0], sum[1]);
        }
    }
    if(succ)
        printf("%d\n", ans);
    else
        printf("-1\n");
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        work();
    }
}