题目大意

现在有 $n$ 个人，他们之间有两种关系：朋友和敌人。我们知道：

• 一个人的朋友的朋友是朋友
• 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

思路

一种并查集的思路。我们可以发现，每一个人有两种身份，别人的朋友或者别人的敌人。那么就可以分情况讨论。如果是朋友的话不说了，最基本的并查集合并。

如果是敌人，那么我就把我敌人的身份与那个敌人连上。这样之后任何人变成了我的敌人都可以反过来找到我的另外的敌人。也就是 merge(u+n,v);merge(v+n,u)，互为敌人。这样以后如果还有人成了 $u$ 的敌人就可以通过 $u+n$ 找到祖先 $v$ 与 $v$ 相连。

代码

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll MAXN = 5000 + 5;
ll f[MAXN * 2], n, m;

ll find(ll u) {
    while (u != f[u]) {
        f[u] = f[f[u]];
        u = f[u];
    }
    return u;
}

void merge(ll u, ll v) {
    f[find(u)] = find(v);
}

int main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= 2 * n; ++i) {
        f[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        char c;
        cin >> c;
        ll u, v;
        scanf("%lld%lld", &u, &v);
        if (c == 'F') {
            merge(u, v);
        } else {
            merge(u + n, v);
            merge(v + n, u);
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (f[i] == i) {
            ans++;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

总结

我们可以发现本题中不变的是人，那么变得就是人们之间的关系了。而关系只有两种，那么分别去考虑即可。
也还有带权并查集的做法。由于并查集本身很类似图论，所以可以通过建边的方式去建立两个点之间的关系，传递权值。