poj 1182 ，并查集拓展域+向量，谈谈个人理解和做法

（~~做这道题因为我认为 -2%3 = 1 ，debug了一个多钟，吨吨吨吨吨。。。~~）

题意：emm题目是中文的

这道题相较于并查集入门题，多了一个集合之间的关系：一样，吃或者被吃，这个时候假如按照传统并查集做法，将全部动物通过并查集分成A,B,C三类将会十分难操作。并查集是快速提供一个集合的关系的做法，假如我们在集合内关系之间存放吃，一样或者被吃这三种关系呢。在做的时候只需要让父节点不一样的搞结合在一起，一样的话就查询关系是不是给出来的关系，不就好了。

可能做法还是有点抽象，我们来看“图”，注意，完整的关系有吃，一样，被吃三种，因此使用0表示一样，吃表示1，被吃表示2，可以结合“图”理解一哈为什么要这么设：

我的理解：（向量加法中，同类的话食性一样，所以同类是0，a吃b，b吃c，所以a被c吃，因此a被c吃是a吃b，b吃c叠加出来的，所以被吃所代表的数字需要是吃的两倍，让1表示吃，则2表示被吃）

好得差不多了，放代码

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=50005;
struct node{
	int fat,relat;// 0:a b same 1: a eat b 2: a eaten by b
}gg[maxn];
int N,K,res;
int trace(int num){ //   !!!
	if(gg[num].fat==num) return num;
	else {		
		int temp=gg[num].fat;
		gg[num].fat=trace(temp);
		gg[num].relat=(3+gg[num].relat+gg[temp].relat)%3;//一定要保证大于0啊
		return gg[num].fat;
	}
}
int main(){
	cin>>N>>K;
	for(int i=1;i<=N;i++){
		gg[i].fat=i;
		gg[i].relat=0;
	}
	res=0;
	while(K--){
		int flag,a,b;
		scanf("%d %d %d",&flag,&a,&b);
		if(a>N||b>N){
			res++; continue;
		}
		if(flag==2&&a==b){
			res++;
			continue;
		}
		int t_a=trace(a),t_b=trace(b);
		if(t_a!=t_b){
			gg[t_b].fat=t_a;
			gg[t_b].relat=(3+gg[a].relat-gg[b].relat-(flag-1))%3;
		}
		else{
			if((3+gg[a].relat-gg[b].relat)%3 != (flag-1)){
				res++;
			} 
		}
	}
	cout<<res;
	return 0;
}

poj 1182 ，并查集拓展域+向量，谈谈个人理解和做法

相关推荐