题目地址：http://poj.org/problem?id=1703
题目大意：警察抓了n个坏蛋，这些坏蛋分别属于龙帮或蛇帮。输入m个语句，A x y询问x和y的关系（在一个帮派，不在，不能确定），D x y表示x和y不在一个帮派。
思路：种类并查集。维护一个数组rel[x]表示x和根节点的关系（0表示在一个帮派，1表示不在），初始全为0（自己和自己在一个帮派），更新rel用偏移量（rel[x]表示px->x，D x y表示x->y=1）。由于2要特判，输入里分三类：1.n==2&&opr=='A' 2.opr=='D' 3.其他【由于至少有两个帮派的人，当n==2是两个人一定分别是两个帮派的，输出为different】【初始化时记得n从1到n】
#include <cstdio> using namespace std; const int N = +;
int fa[N], rel[N]; void init(int n)
{
for(int i = ; i <= n; i++)
{
fa[i] = i;
rel[i] = ;
}
} //注意下查找时更新rel[]里那个px
int found(int x)
{
if(fa[x] == x)
return x;
int px = fa[x];
fa[x] = found(fa[x]);
rel[x] = (rel[px]+rel[x])%;
return fa[x];
} void unite(int x, int y)
{
int px = found(x);
int py = found(y);
if(px != py)
{
fa[py] = px;
rel[py] = (rel[x]++-rel[y])%;
}
} int main()
{
int n, m, t, a, b;
char opr;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
init(n);
for(int i = ; i < m; i++)
{
getchar();
scanf("%c%d%d", &opr, &a, &b);
if(n == && opr =='A')//2要特判。分类一共是A2、其他A、D
{
printf("In different gangs.\n");
}
else if(opr == 'D')
unite(a, b);
else
{
int pa = found(a);
int pb = found(b);
if(pa != pb)
printf("Not sure yet.\n");
else if(rel[a] == rel[b])
printf("In the same gang.\n");
else
printf("In different gangs.\n");
}
}
}
return ;
}
【特判2wa了好久!!!!!!!!!!!!!!!!!!!初始化函数也写错了。。刚开始写成<n了!!!!!!!!!!!】