HDU1272 小希的迷宫(并查集判正环)

题目链接

思路

选用并查集判断是否形成环与是否全部连通即可，如果两个点父节点相同，则必定成环，连通则可以通过i==pre[i]的数量进行判断。

代码

#include<map>
#include<stack>
#include<queue>
#include<string>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define pb push_back
using namespace std;
const int P=1e9+5;
const int mod=1e9+7;
const int maxn=1e6+5;
typedef long long ll;
const int inf=0x3f3f3f3f;
bool vis[maxn];
int u,v,ca,cnt,flag,pre[maxn];
int find(int x)
{
	return x==pre[x]?x:pre[x]=find(pre[x]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	while(cin>>u>>v)
	{
		if(u==v&&u==-1)
			break;
		if(ca==0)
		{
			if(u==0&&v==0)
			{
				cout<<"Yes"<<endl;
				continue;
			}
			for(int i=0;i<=100005;i++)
				pre[i]=i;
			ca++;
			
		}
		if(u!=0&&v!=0)
		{
			vis[u]=true;
			vis[v]=true;
			int fu=find(u);
			int fv=find(v);
			if(fu!=fv)
				pre[fu]=fv;
			else
			{
				flag=1;
				continue;
			}
		}
		else if(u==0&&v==0)
		{
			ca=0;
			cnt=0;
			for(int i=0;i<=100005;i++)
			{
				if(vis[i]==true)
				{
					vis[i]=false;
					if(pre[i]==i)
						cnt++;
				}
			}
			if(flag||cnt!=1)
			{
				flag=0;
				cout<<"No"<<endl;
			}
			else
				cout<<"Yes"<<endl;
		}
	}
    return 0;
}