K - Find them, Catch them POJ - 1703 (带权并查集)

题目链接:

K - Find them, Catch them

POJ - 1703

题目大意:警方决定捣毁两大犯罪团伙:龙帮和蛇帮,显然一个帮派至少有一人。该城有N个罪犯,编号从1至N(N<=100000。将有M(M<=100000)次操作。
D a b 表示a、b是不同帮派
A a b 询问a、b关系。

具体思路:带权并查集模板题。一般并查集都是相同的放在一个联通块里面。对于这个题,我们可以利用一下这个性质,只要是有联系的,都放进一个连通块里面,然后我们查询的时候,如果说他们的祖先一样的话,就首先能够保证是有关系的。然后就开始判断是敌对关系还是朋友关系。我们再加一个数组r[x],表示x和他的祖先的关系,如果r[x]=1代表和祖先是敌对关系,否则就是朋友关系。然后在寻找路径的过程中,不停地更新就可以了。

 #include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = 2e5+;
int father[maxn];
int r[maxn];
int Find(int t)
{
if(t==father[t])
return t;
int tmp=father[t];
father[t]=Find(father[t]);
r[t]=(r[tmp]+r[t])%;
return father[t];
}
void match(int t1,int t2)
{
int s1=Find(t1);
int s2=Find(t2);
father[s1]=s2;
r[s1]=(r[t1]+r[t2]+)%;//t1和t2是敌对关系
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=; i<=n; i++)
{
father[i]=i;
r[i]=;
}
char str[];
int st,ed;
while(m--)
{
scanf("%s",str);
if(str[]=='A')
{
scanf("%d %d",&st,&ed);
if(Find(st)==Find(ed))
{
if(r[st]==r[ed])
{
printf("In the same gang.\n");
}
else
printf("In different gangs.\n");
}
else
{
printf("Not sure yet.\n");
}
}
else
{
scanf("%d %d",&st,&ed);
match(st,ed);
}
}
return ;
}
}
上一篇:SQL server 表中如何创建索引?


下一篇:mysql 8.0 改变数据目录和日志目录(二)