文章目录
带权并查集
在基础并查集上增加了权值，在对并查集进行路径压缩和合并操作时，这些权值具有一定属性，即可将他们与父节点的关系，变化为与所在树的根结点关系。
也就是说，权值代表着当前节点与父节点的某种关系（即使路径压缩了也是这样），通过两者关系，也可以将同一棵树下两个节点的关系表示出来。
个人感觉比较难理解。
种类并查集
元素分为不同种类的并查集，实际上可以转化为带权并查集来处理。当然也有种类并查集自己的解法，常见的做法是分为 n 个种类，就将原并查集扩大 n 倍规模。
一般就几个状态而已，做法比较好理解。
例题
【POJ】1703 Find them, Catch them
原题链接：http://poj.org/problem?id=1703
题意： 一个城市有两个帮派，n，k 分别表示 n 个人，k 次询问。例如， A 1 2 是询问 1 和 2 这两个人是不是一个帮派，然后输出。D 1 2 是表示这两个人不在一个帮派。
注意： 再次因为没加 getchar() 被卡了好久，一直报RE错误。。。这个坑下次一定不能再掉了。。。还有，要用 scanf、printf 输入输出格式，不然会TLE。
1、种类并查集做法：
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100100;
int n,m;
int r[N*2];
int find(int x){
if(r[x]==x)
return x;
else
return r[x]=find(r[x]);
}
void merge(int x,int y){
int ra=find(x);
int rb=find(y);
if(ra!=rb)
r[ra]=rb;
}
bool same(int a,int b){
return find(a)==find(b);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=2*N;i++)
r[i]=i;
while(m--){
//再次在这里掉坑！！！谨记！！不加这个会RE或者WA，凡是样例能过！！！
getchar();
char ch;
scanf("%c",&ch);
int a,b;
scanf("%d%d",&a,&b);
if(ch=='D'){
merge(a,b+n);
merge(a+n,b);
}else{
if(same(a,b)){ //a、b同类
printf("In the same gang.\n");
continue;
}
if(same(a,b+n)) //a、b不同类
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
}
}
}
return 0;
}
2、带权并查集做法：
【POJ】1182 食物链
原题链接：http://poj.org/problem?id=1182
题意： 中文题目，自己看原题即可，这里就不啰嗦了。
思路： 这道题可以用种类并查集来解，也可以用带权并查集来做。要注意的就是要用 scanf、printf 输入输出格式，不然会TLE。
1、种类并查集做法：
推荐大佬的博客：POJ - 1182： 食物链 （并查集）
#include <iostream>
#include <cstdio>
using namespace std;
const int N=50010;
int n,k;
int r[N*3];
int find(int x){
int t=x;
while(r[t]!=t)
t=r[t];
while(x!=t){ //路径压缩
int temp=r[x];
r[x]=t;
x=temp;
}
return t;
}
void merge(int x,int y){
int roota=find(x);
int rootb=find(y);
if(roota != rootb)
r[roota]=rootb;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=3*n;i++)
r[i]=i;
int ans=0;
for(int i=1;i<=k;i++){
int op,a,b;
scanf("%d%d%d",&op,&a,&b);
if(a<1||a>n||b<1||b>n){ //不在范围内，假话
ans++;
continue;
}
if(op==2 && a==b){ // 如果是同类，a还吃b，假话
ans++;
continue;
}
if(op==1){ //a、b同类
if(find(a)==find(b+n) || find(b)==find(a+n)) //如果a吃b或者b吃a，假话
ans++;
else{ //真话，建立a和b同类的关系
merge(a,b);
merge(a+n,b+n);
merge(a+2*n,b+2*n);
}
}else if(op==2){ //a吃b
if(find(a)==find(b) || find(b)==find(a+n)) ///如果a、b同类或者b吃a，假话
ans++;
else{ //真话，建立a吃b的关系
merge(a,b+n);
merge(a+n,b+2*n);
merge(a+2*n,b);
}
}
}
printf("%d\n",ans);
return 0;
}
2、带权并查集做法：
推荐大佬的博客：
#include <iostream>
#include <cstdio>
using namespace std;
const int N=50010;
int n,k;
int r[N],rel[N];
void init(){
for(int i=1;i<=n;i++){
r[i]=i;
rel[i]=0;
}
}
int find(int x){
if(x==r[x])
return x;
int t=r[x];
r[x]=find(t);
rel[x]=(rel[x]+rel[t])%3;
return r[x];
}
int main(){
scanf("%d%d",&n,&k);
init();
int ans=0;
int op,a,b;
for(int i=1;i<=k;i++){
scanf("%d%d%d",&op,&a,&b);
if(a>n || b>n){
ans++;
continue;
}
if(op==2 && a==b){
ans++;
continue;
}
int roota=find(a);
int rootb=find(b);
if(roota != rootb){
r[rootb]=roota;
rel[rootb]=(3+(op-1)+rel[a]-rel[b])%3;
}else{
if(op==1 && rel[a]!=rel[b])
ans++;
else if(op==2 && (3-rel[a]+rel[b])%3!=op-1)
ans++;
}
}
printf("%d",ans);
return 0;
}