题目传送门(BZOJ)
>原文链接<

题解 :

只要考虑如何维护题中所述的两个关系就好了。

  1. 我朋友的朋友也是我的朋友

    —— 并查集,这三个人只要在同一个集合里,就意味着他们都是朋友。

    1. 我敌人的敌人是我的朋友。

    ——我们把每个人拆点,如果 $a$ 和 $b$ 是敌人,那么把 $a’$ 和 $b$ 并到一个集合里,$b’$ 和 $a$ 同理。

    这样如果再有人是 $a$ 的敌人,就会和 $a’$ 合并,也就是 $b$ 的朋友了

最后统计一下前 $n$ 个点中有多少个不同的集合就可以辣。

代码 :

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 2100;int fa[N], a[N];int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}int main() { int n, q; scanf("%d%d", &n, &q); for(int i = 1; i <= n*2; i ++ ) fa[i] = i; for(int i = 1; i <= q; i ++ ) { char opt[3]; scanf("%s", opt); if(opt[0] == 'E') { int x, y; scanf("%d%d", &x, &y); fa[find(x+n)] = find(y); fa[find(y+n)] = find(x); } else { int x, y; scanf("%d%d", &x, &y); fa[find(x)] = find(y); } } for(int i = 1; i <= n; i ++ ) a[i] = find(i); sort(a+1, a+n+1); int ans = 0; for(int i = 1; i <= n; i ++ ) if(a[i] != a[i-1]) ans ++ ; printf("%d\n", ans);}