2019湘潭校赛 G（并查集）

要点

• 题目传送
• 题目本质是每个点必属于两个集合中的一个，伴随的性质是：如果一个人说别人true，则他们一定属于同一阵营；如果说别人fake，一定不属于同一阵营。
• 每个点拆为\(i\)和\(i + n\)分别代表他属于某种阵营（目前还不确定），然后根据上述性质边读入边合并同类。
• 这样扫一遍，如果某个\(i\)和\(i + n\)属于同一阵营则矛盾，无解。
• 若有解，对于每个点扫一遍和他同阵营的人，为了使fakeman尽可能地少，\(<=n\)的人少就把\(<=n\)视为fakeman；否则把\(>n\)的视为fakeman。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int T, n, m;

int f[maxn << 1], ans[maxn], sz[maxn << 1];

vector<int> v[maxn << 1];

int getf(int v) {

    return v == f[v] ? v : f[v] = getf(f[v]);

}

void merge(int u, int v) {

    f[getf(u)] = getf(v);

}

int main() {

    for (scanf("%d", &T); T--;) {

        scanf("%d %d", &n, &m);

        for (int i = 1; i <= n * 2; i++)    f[i] = i, v[i].clear();

        memset(ans, 0, sizeof ans);

        memset(sz, 0, sizeof sz);

        for (int i = 1, u, v, w; i <= m; i++) {

            scanf("%d %d %d", &u, &v, &w);

            if (w)    merge(u, v), merge(u + n, v + n);

            else    merge(u, v + n), merge(u + n, v);

        }

        int flag = 1;

        for (int i = 1; i <= n; i++)

            if (getf(i) == getf(i + n)) {

                flag = 0; break;

            }

        if (!flag) {

            puts("-1"); continue;

        }

        for (int i = 1; i <= n * 2; i++)    v[getf(i)].push_back(i);

        for (int i = 1; i <= n; i++)    sz[getf(i)]++;

        for (int i = 1; i <= n; i++) {

            if (ans[i])    continue;

            int fa = getf(i);

            if (v[fa].size() - sz[fa] >= sz[fa]) {

                for (int j : v[fa])

                    if (j > n)    ans[j - n] = 2;

                    else    ans[j] = 1;

            } else {

                for (int j : v[fa])

                    if (j > n)    ans[j - n] = 1;

                    else    ans[j] = 2;

            }

        }

        for (int i = 1; i <= n; i++)    printf("%d", ans[i] - 1);

        puts("");

    }

}