题意:
两个犯罪团伙:一个帮派至少有一人。
有N个罪犯,编号从1 至 N (N<=100000)。不知道具体属于哪一个团伙。
有M(M<=100000)次操作。
D a b 表示a、b是不同帮派
A a b 询问a、b关系
第一行是数据总数 T (1 <= T <= 20)
每组数据第一行是N、M,接下来M行是操作
对于每一个A操作,回答:
"In the same gang."
"In different gangs."
"Not sure yet."
分析:
是最简单的带权值并查集,和poj1182很像,
poj1182
只要理解了1182这个题,那么这一题就简单了。
权值记录了集合中每个节点之间的关系。
这一题只有两种关系,同帮派,不同帮派。
可以分别用数字 0 1 表示这两种关系。
然后还是利用路径压缩的过程计算出每个节点个根节点的关系。
公式和1182一样,
通过根节点可以计算集合中任意两个节点之间的关系。
这样一来,对于每一次询问A操作,计算他们的关系判断是不是 0 .
对于每一次 D 操作,把 a , b 加入集合,并且跟新集合中的关系。
这一点和1182也一样。
代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e5+10;
int r[MAXN];
int rel[MAXN];
void init(int n)
{
for (int i = 1; i <= n; i++){
r[i] = i; rel[i] = 0;
}
}
int Find(int x)
{
if (x == r[x])
return r[x];
else
{
int t = r[x];
r[x] = Find(r[x]);
rel[x] = (rel[x]+rel[t]) % 2;
return r[x];
}
}
void Join(int a, int b)
{
int ra = Find(a);
int rb = Find(b);
if (ra != rb)
{
r[ra] = rb;
rel[ra] = (1+rel[b]-rel[a]+2)%2;
}
}
int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
char c[2];
int T, n ,m, a, b, f;
cin >> T;
while(T--)
{
cin >> n >> m;
init(n);
for (int i = 0; i < m; i++)
{
scanf("%s %d %d", &c, &a, &b);
if (c[0] == 'D') {
Join(a, b);
} else {
if (Find(a)==Find(b)&&(rel[a]-rel[b]+2)%2==0)
cout << "In the same gang." << endl;
else if (Find(a)==Find(b))
cout << "In different gangs." << endl;
else
cout << "Not sure yet." << endl;
}
}
}
return 0;
}
Comments | NOTHING