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).
然后就是统计并查集队长数目的问题了。
#include<stdio.h>
#include<string.h>
int N,M;
][]={};
];
]; //t 用于标记独立块的根结点
int Find(int x);
void mix(int x,int y);
int main(int argc, char *argv[])
{
int i,j,k,p,q;
];
;
freopen("data2.in","r",stdin);
scanf("%d%d",&N,&M);getchar();
//printf("%d %d\n",N,M);
;i<=N;i++)//并查集的初始化,每一个节点一开始都是各自独立的
pre[i]=i;
;i<M;i++)
{
scanf("%s %d %d",temp,&p,&q);getchar();
//printf("%c %d %d\n",temp[0],p,q);
]=='F')
{
a[p][q]=; a[q][p]=;
}
]=='E')
{
a[p][q]=; a[q][p]=;
}
}
;i<=N;i++)
{
;j<=N;j++)
{
)
{
;k<=N;k++)
) { a[i][k]=; a[k][i]=; }
}
}
}
;i<=N;i++)
{
;j<=N;j++)
{
) mix(i,j);
}
}
memset(t,,sizeof(t));
;i<=N;i++) //标记根结点（作为掌门（队长）的节点会被标记为1.比如编号i的节点做掌门，则t[i]=1）
{ t[Find(i)]=; }
,i=;i<=N;i++) //统计掌门（队长）的人数（就是队伍的数量）
if(t[i]) ans++;
printf("%ld\n",ans);
;
}
int Find(int x)
{
int r=x;
while(r!=pre[r])
r=pre[r];
int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}
代码二：
在输入海盗p和q的关系信息时：若p和q是朋友，则直接做并查集的合并操作；若p和q是敌人关系则需要记录p和q各自第一次输入的敌人，然后下一次再输入p和q的敌人，则把新输入的敌人与第一次输入的敌人做并查集的朋友关系合并。（注意：朋友的朋友是朋友，敌人的敌人是朋友。）
但是，这个地方需要注意：用f[p]记录p第一次遇到的敌人q，同时也要用f[q]记录q第一次遇到的敌人p。
重点就是这一段：
;i<M;i++)
{
scanf("%s %d %d",temp,&p,&q);getchar();
//printf("%c %d %d\n",temp[0],p,q);
]=='F')
{
mix(p,q);
}
]=='E')
{
) f[p]=q;//记录p第一次遇到的敌人q
else mix(q,f[p]); //遇到p的其他敌人时，把新遇到的敌人q与最开始遇到的敌人f[q]设为朋友关系（因为这两人都是p的敌人，所以两人是朋友）
) f[q]=p;//同样地，要记录q首次遇到的敌人
else mix(p,f[q]); //遇到q的其他敌人时，将新遇到的敌人与首次遇到的敌人f[p]设为朋友
}
}
完整代码如下：
#include<stdio.h>
#include<string.h>
int N,M;
][]={};
]={};
];
]; //t 用于标记独立块的根结点
int Find(int x);
void mix(int x,int y);
int main(int argc, char *argv[])
{
int i,j,k,p,q;
];
;
freopen("data2.in","r",stdin);
scanf("%d%d",&N,&M);getchar();
//printf("%d %d\n",N,M);
;i<=N;i++)//并查集的初始化,每一个节点一开始都是各自独立的
pre[i]=i;
;i<M;i++)
{
scanf("%s %d %d",temp,&p,&q);getchar();
//printf("%c %d %d\n",temp[0],p,q);
]=='F')
{
mix(p,q);
}
]=='E')
{
) f[p]=q;
else mix(q,f[p]);
) f[q]=p;
else mix(p,f[q]);
}
}
memset(t,,sizeof(t));
;i<=N;i++) //标记根结点（作为掌门（队长）的节点会被标记为1.比如编号i的节点做掌门，则t[i]=1）
{
t[Find(i)]=;
}
,i=;i<=N;i++) //统计掌门（队长）的人数（就是队伍的数量）
if(t[i]) ans++;
printf("%d\n",ans);
;
}
int Find(int x)
{
int r=x;
while(r!=pre[r])
r=pre[r];
int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}
另一种思路：在输入海盗关系信息时，用一个二维的数组f[i][j]的第i行记录海盗i的所有敌人的编号。
输入完所有关系信息以后，扫描f数组的每一行，将每一行里面的人设为朋友（做并查集的合并操作）。这个应该也是可以的，但没有上面代码二的思路好，这里就不写了。