1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：
我朋友的朋友是我的朋友；
我敌人的敌人也是我的朋友。
两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。
输入文件gangs.in的第一行是一个整数N(2<=N<=1000)，表示强盗的个数（从1编号到N）。 第二行M(1<=M<=5000)，表示关于强盗的信息条数。 以下M行，每行可能是F p q或是E p q（1<=p q<=N），F表示p和q是朋友，E表示p和q是敌人。输入数据保证不会产生信息的矛盾。
输出文件gangs.out只有一行，表示最大可能的团伙数。
6
4
E 1 4
F 3 5
F 4 6
E 1 2
3
2<=N<=1000
1<=M<=5000
1<=p q<=N
解题分析：
考查的是并查集。
吐槽一下：这道题可以在codevs、luogu提交测试，测试的数据应该是一样的。但是我严重怀疑后台的输入数据文件格式有问题。输入海盗的信息时，必须用字符串输入海盗p和q的朋友或敌人关系，不能用字符的方式输入，否则就无法AC了。
代码一：
输入海盗的关系信息时，将海盗关系信息存储在一个类似于图的邻接矩阵a[ ][ ]中（a数组初始是全部是0）：
若海盗p和q是朋友则a[p][q]和a[q][p]置1；若p和q是敌人则a[p][q]=2; a[q][p]=2;
然后扫描二维数组a，若i和j为敌人关系（即a[i][j]==2），则扫描a数组第j行寻找j的所有敌人k（即a[j][k]==2），然后把i和k设为朋友，即：设置a[i][k]=1;
接下来，扫描a数组，利用并查集把所有朋友关系合并，即：若a[i][j]==1则执行mix(i,j).
然后就是统计并查集队长数目的问题了。
1 #include<stdio.h> 2 #include<string.h> 3 int N,M; 4 int a[1020][1020]={0}; 5 6 int pre[1050]; 7 bool t[1050]; //t 用于标记独立块的根结点 8 9 int Find(int x); 10 void mix(int x,int y); 11 12 int main(int argc, char *argv[]) 13 { 14 int i,j,k,p,q; 15 char temp[100]; 16 int ans=0; 17 freopen("data2.in","r",stdin); 18 19 scanf("%d%d",&N,&M);getchar(); 20 //printf("%d %d\n",N,M); 21 for(i=1;i<=N;i++)//并查集的初始化,每一个节点一开始都是各自独立的 22 pre[i]=i; 23 for(i=0;i<M;i++) 24 { 25 scanf("%s %d %d",temp,&p,&q);getchar(); 26 //printf("%c %d %d\n",temp[0],p,q); 27 if(temp[0]=='F') 28 { 29 a[p][q]=1; a[q][p]=1; 30 } 31 else if(temp[0]=='E') 32 { 33 a[p][q]=2; a[q][p]=2; 34 } 35 } 36 37 for(i=1;i<=N;i++) 38 { 39 for(j=1;j<=N;j++) 40 { 41 if(a[i][j]==2) 42 { 43 for(k=1;k<=N;k++) 44 if(a[j][k]==2) { a[i][k]=1; a[k][i]=1; } 45 } 46 } 47 } 48 49 for(i=1;i<=N;i++) 50 { 51 for(j=1;j<=N;j++) 52 { 53 if(a[i][j]==1) mix(i,j); 54 } 55 } 56 memset(t,0,sizeof(t)); 57 for(i=1;i<=N;i++) //标记根结点（作为掌门（队长）的节点会被标记为1.比如编号i的节点做掌门，则t[i]=1） 58 { t[Find(i)]=1; } 59 for(ans=0,i=1;i<=N;i++) //统计掌门（队长）的人数（就是队伍的数量） 60 if(t[i]) ans++; 61 printf("%ld\n",ans); 62 return 0; 63 } 64 65 int Find(int x) 66 { 67 int r=x; 68 while(r!=pre[r]) 69 r=pre[r]; 70 71 int i=x,j; 72 while(pre[i]!=r) 73 { 74 j=pre[i]; 75 pre[i]=r; 76 i=j; 77 } 78 return r; 79 } 80 void mix(int x,int y) 81 { 82 int fx=Find(x),fy=Find(y); 83 if(fx!=fy) 84 { 85 pre[fy]=fx; 86 } 87 }
代码二：
在输入海盗p和q的关系信息时：若p和q是朋友，则直接做并查集的合并操作；若p和q是敌人关系则需要记录p和q各自第一次输入的敌人，然后下一次再输入p和q的敌人，则把新输入的敌人与第一次输入的敌人做并查集的朋友关系合并。（注意：朋友的朋友是朋友，敌人的敌人是朋友。）
但是，这个地方需要注意：用f[p]记录p第一次遇到的敌人q，同时也要用f[q]记录q第一次遇到的敌人p。
重点就是这一段：
for(i=0;i<M;i++) { scanf("%s %d %d",temp,&p,&q);getchar(); //printf("%c %d %d\n",temp[0],p,q); if(temp[0]=='F') { mix(p,q); } else if(temp[0]=='E') { if(f[p]==0) f[p]=q;//记录p第一次遇到的敌人q else mix(q,f[p]); //遇到p的其他敌人时，把新遇到的敌人q与最开始遇到的敌人f[q]设为朋友关系（因为这两人都是p的敌人，所以两人是朋友） if(f[q]==0) f[q]=p;//同样地，要记录q首次遇到的敌人 else mix(p,f[q]); //遇到q的其他敌人时，将新遇到的敌人与首次遇到的敌人f[p]设为朋友 } }
完整代码如下：
1 #include<stdio.h> 2 #include<string.h> 3 int N,M; 4 int a[1020][1020]={0}; 5 int f[1020]={0}; 6 7 int pre[1050]; 8 bool t[1050]; //t 用于标记独立块的根结点 9 10 int Find(int x); 11 void mix(int x,int y); 12 13 int main(int argc, char *argv[]) 14 { 15 int i,j,k,p,q; 16 char temp[100]; 17 int ans=0; 18 freopen("data2.in","r",stdin); 19 20 scanf("%d%d",&N,&M);getchar(); 21 //printf("%d %d\n",N,M); 22 for(i=1;i<=N;i++)//并查集的初始化,每一个节点一开始都是各自独立的 23 pre[i]=i; 24 for(i=0;i<M;i++) 25 { 26 scanf("%s %d %d",temp,&p,&q);getchar(); 27 //printf("%c %d %d\n",temp[0],p,q); 28 if(temp[0]=='F') 29 { 30 mix(p,q); 31 } 32 else if(temp[0]=='E') 33 { 34 if(f[p]==0) f[p]=q; 35 else mix(q,f[p]); 36 if(f[q]==0) f[q]=p; 37 else mix(p,f[q]); 38 } 39 } 40 41 memset(t,0,sizeof(t)); 42 for(i=1;i<=N;i++) //标记根结点（作为掌门（队长）的节点会被标记为1.比如编号i的节点做掌门，则t[i]=1） 43 { 44 t[Find(i)]=1; 45 } 46 for(ans=0,i=1;i<=N;i++) //统计掌门（队长）的人数（就是队伍的数量） 47 if(t[i]) ans++; 48 printf("%d\n",ans); 49 return 0; 50 } 51 52 int Find(int x) 53 { 54 int r=x; 55 while(r!=pre[r]) 56 r=pre[r]; 57 58 int i=x,j; 59 while(pre[i]!=r) 60 { 61 j=pre[i]; 62 pre[i]=r; 63 i=j; 64 } 65 return r; 66 } 67 void mix(int x,int y) 68 { 69 int fx=Find(x),fy=Find(y); 70 if(fx!=fy) 71 { 72 pre[fy]=fx; 73 } 74 }
另一种思路：在输入海盗关系信息时，用一个二维的数组f[i][j]的第i行记录海盗i的所有敌人的编号。
输入完所有关系信息以后，扫描f数组的每一行，将每一行里面的人设为朋友（做并查集的合并操作）。这个应该也是可以的，但没有上面代码二的思路好，这里就不写了。
