| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 30702 | Accepted: 9447 |
Description
two criminals; do they belong to a same clan?
You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.)
Assume N (N <= 10^5) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M <= 10^5) messages in sequence, which are in the following two kinds:
1. D [a] [b]
where [a] and [b] are the numbers of two criminals, and they belong to different gangs.
2. A [a] [b]
where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.
Input
Output
Sample Input
1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4
Sample Output
Not sure yet.
In different gangs.
In the same gang.
题意：
城市里面有2个犯罪团伙，罪犯都属于这两个团伙。如今给你2个罪犯，推断他们是不是一个犯罪团伙。假设当前关系不确定，就输出not sure yet.
并查集的应用，非常A bug's life基本一样。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath> using namespace std; const int maxn = 100005;
int cas, n, m;
int parent[maxn], relation[maxn];
char str[2];
int a, b; int find(int x)
{
if (x == parent[x])
return x;
int px = find(parent[x]);
relation[x] = ((relation[x] + relation[parent[x]])%2);
return parent[x] = px;
} void init()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
parent[i] = i;
relation[i] = 0;
}
} void kruskal(int a, int b)
{
if(n==2 && str[0]=='A')
//题意是说仅仅有两个人时，应该是属于不同的团伙。。可是数据没有这个。。就算不加也A了、、
printf("In different gangs.\n");
else
{
int pa = find(a);
int pb = find(b);
if (pa != pb)
{
if (str[0] == 'D')
{
parent[pa] = pb;
if (relation[b] == 0)
relation[pa] = 1 - relation[a];//表示不同
else
relation[pa] = relation[a];//同样
}
else printf("Not sure yet.\n");
}
else
{
if (str[0] == 'A')
{
if (relation[a] != relation[b])
printf("In different gangs.\n");
else
printf("In the same gang.\n");
}
}
}
} int main()
{
scanf("%d", &cas);
while (cas--)
{
init();
while (m--)
{
scanf("%s%d%d", str, &a, &b);
kruskal(a, b);
}
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。