题目链接

http://poj.org/problem?id=1703

题意

有两个帮派:龙帮和蛇帮,两个帮派共有n个人(编号1~n),输入m组数据,每组数据为D [a][b]或A [a][b],D[a][b]表示a,b属于不同的帮派,A [a][b]则让我们判断a,b是否属于一个帮派,根据判断的结果进行相应的输出。

思路

这题和poj2492很像,使用并查集解决,方法我已在poj2492的题解中写出,这里不再赘述。

代码

 #include <cstdio>
using namespace std; const int N = + ;
int p[N];
int r[N]; void make_set(int n)
{
for (int i = ;i <= n;i++)
{
p[i] = -;
r[i] = ;
}
} int find_root(int x)
{
if (p[x] == -)
return x; int t = p[x];
p[x] = find_root(p[x]);
r[x] = (r[x] + r[t]) % ;
return p[x];
} void union_set(int a, int b)
{
int ra = find_root(a);
int rb = find_root(b); if (ra != rb)
{
p[ra] = rb;
r[ra] = (r[a] + r[b] + ) % ;
}
} int main()
{
//freopen("poj1703.txt", "r", stdin);
int t;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
make_set(n);
char c;
int a, b;
for (int i = ;i < m;i++)
{
getchar();
scanf("%c%d%d", &c, &a, &b);
if (c == 'A')
{
if (find_root(a) == find_root(b)) //a,b在一个集合里
{
if (r[a] == r[b]) //a,b为同一帮派
puts("In the same gang.");
else puts("In different gangs."); //a,b为不同帮派
}
else puts("Not sure yet."); //a,b不再同一集合里,故不确定
}
else union_set(a, b);
}
}
return ;
}

注意点

1、函数union_set要写成这样:

//正确写法
void union_set(int a, int b)
{
int ra = find_root(a);
int rb = find_root(b); if (ra != rb)
{
p[ra] = rb;
r[ra] = (r[a] + r[b] + ) % ;
}
}

写成如下形式会MLE:

//错误写法,MLE
void union_set(int a, int b)
{
int ra = find_root(a);
int rb = find_root(b); p[ra] = rb;
r[ra] = (r[a] + r[b] + ) % ;
}

2、使用scanf输入。

相似题目

1、poj2492

05-01 04:20