[poj1703]Find them, Catch them(种类并查集)

时间:2024-09-09 20:07:56

题意:食物链的弱化版本

解题关键:种类并查集,注意向量的合成。

$rank$为1代表与父亲对立,$rank$为0代表与父亲同类。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long ll;
#define M 100005
int fa[M],rank1[M];
int find1(int x){
if(x==fa[x]) return x;
int tmp=fa[x];
fa[x]=find1(tmp);
rank1[x]=(rank1[x]+rank1[tmp])%;
return fa[x];
}
void unite(int x,int y){
int t=find1(x);
int t1=find1(y);
if(t!=t1){//合并的时候需要用到向量的合成和差
fa[t1]=t;
rank1[t1]=(-rank1[y]+rank1[x])%;
}
}
char ch[];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
fa[i]=i;
rank1[i]=;
}
for(int i=;i<m;i++){
int tmp,tmp1;
scanf("%s%d%d",ch,&tmp,&tmp1);
if(ch[]=='D') unite(tmp,tmp1);
else{
int x=find1(tmp);
int y=find1(tmp1);
if(x==y){//可以判断出关系
int r=(-rank1[tmp]+rank1[tmp1])%;
if(r==) printf("In the same gang.\n");
else printf("In different gangs.\n");
}
else printf("Not sure yet.\n");
}
}
}
return ;
}

法二:$fa$数组代表$i$属于$A$或$i$属于$B$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=;
int fa[maxn*];
int find1(int x){
int r=x;
while(r!=fa[r]) r=fa[r];
int i=x,j;
while(i!=r){
j=fa[i];
fa[i]=r;
i=j;
}
return r;
} void unite(int x,int y){
x=find1(x),y=find1(y);
if(x!=y) fa[x]=y;
} int main(){
int T;
scanf("%d",&T);
while(T--){
int N,M,x,y;
char opt[];
scanf("%d%d",&N,&M);
for(int i=;i<=*N;i++) fa[i]=i;
while(M--){
scanf("%s%d%d",opt,&x,&y);
if(opt[]=='A'){
if(find1(x)==find1(y)) printf("In the same gang.\n");
else if(find1(x)==find1(y+N)&&find1(x+N)==find1(y)) printf("In different gangs.\n");
else printf("Not sure yet.\n");
}
else{
unite(x,y+N);
unite(x+N,y);
}
}
}
return ;
}