这题先从题面入手，很明显是一个并查集的题目，题面中提到了“我朋友的朋友是我的朋友；我敌人的敌人也是我的朋友。两个强盗是同一团伙的条件是当且仅当他们是朋友。”
这让我联想到了[NOI2002]食物链那一题，同样是多种关系，那一题是通过开三倍空间的并查集来解决三种不同关系的操作，所以说这题也可以效仿，开两倍空间。F[x]为x的朋友，F[x+n]为x的敌人，如果说是朋友，那么便合并F[x]与F[y]，如果是敌人，则合并F[x+n]与y，F[y+n]与x，这一步的目的是将敌人指向自己。
代码实现：
1 #include <cstdio> 2 #include <iostream> 3 #include <cctype> 4 #define MAXN (10000+10) 5 #define _for(i,a,b) for (register int i = a;i <= b;i++) 6 7 inline int read() { 8 int a = 0,f = 1; 9 char v= getchar(); 10 while(!isdigit(v)) { 11 if (v == '-') { 12 f = -1; 13 } 14 v = getchar(); 15 } 16 while (isdigit(v)) { 17 a = a * 10 + v - 48; 18 v = getchar(); 19 } 20 return a * f; 21 } 22 23 int f[MAXN*2],N,M,total;//f[a]表示的是a的朋友，f[2*a]表示a的敌人 24 25 int find(int x) { 26 if (f[x] == x) return x; 27 return f[x] = find(f[x]); 28 } 29 30 inline void mix(int a,int b) { 31 int aa = find(a),bb = find(b); 32 if (aa != bb) { 33 f[aa] = bb; 34 } 35 } 36 37 inline void init(int n) { 38 _for(i,1,n*2) { 39 f[i] = i; 40 } 41 } 42 int main() { 43 N = read(),M = read(); 44 init(N); 45 _for(i,1,M) { 46 char p; 47 std::cin >> p; 48 int x = read(),y = read(); 49 if (p == 'F') { 50 mix(x,y); 51 } 52 if (p == 'E') { 53 mix(x+N,y); 54 mix(y+N,x); 55 } 56 } 57 _for(i,1,N) { 58 if (f[i] == i) { 59 total++; 60 } 61 } 62 printf("%d",total); 63 return 0; 64 }