博客

开启了一个新思路！！woc！！对于二分图的判定，我竟然用并查集就能解决？？

之前对于二分图的判定一直有点蒙蔽，

离散老师讲的着色法，我也没有实现

，就一直放着了，但是最近学的这一个并查集！！竟然解决了？？！！

简单的copy了一下代码，找了一些题，竟然都过了，

hihocoder#1121-二分图判定：

http://hihocoder.com/problemset/problem/1121

就是直接复制粘贴？？发现跟

https://blog.csdn.net/qq_40482358/article/details/86809694

这个代码一样？？这也太秀了把

还有一个NYOJ-1015，之前一直没有过，这次直接Ctrl+C，Ctrl+V，AC！

AC板子：

const int MAXN=1e4+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);

struct node{
	int pre,relation;
}f[MAXN];
int n,m,flag;

void intt(){
	for(int i=1;i<=n;++i){
		f[i].pre=i;
		f[i].relation=0;
	}flag=0;
}
int Find(int a){
	if(f[a].pre==a){
		return a;
	}int temp=f[a].pre;
	f[a].pre=Find(f[a].pre);
	f[a].relation=(f[temp].relation+f[a].relation)%2;
	return f[a].pre;
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		int a,b;intt();
		for(int i=1;i<=m;++i){
			scanf("%d%d",&a,&b);
			if(flag==1)	continue;
			int aa=Find(a),bb=Find(b);
			if(aa==bb){//有同样的对象 
				if(f[a].relation==f[b].relation)
					flag=1;//发现同性恋 
			}
			if(aa!=bb){//对象不同 
				f[aa].pre=bb;
				f[aa].relation=(2-f[a].relation+1+f[b].relation)%2;
			}
		}
		if(flag)	printf("Wrong\n");
		else	printf("Correct\n");
	}
}

什么？？你问我向量并查集是什么东西？？一个神仙发现的算法方案，具体入坑，请移步POJ-1182-食物链，

讨论区有很多大佬，我这里有我的解决方法，想看代码的戳一下：

https://blog.csdn.net/qq_40482358/article/details/86777178

。