欧拉回路的判断(hdu1878)其一

输入若干测试用例，判定一个无向图是否有欧拉回路。
此题是无向图，无向图的欧拉回路需要满足两个条件，一是图是连通的，二是各个结点度数为偶数。
程序中用并查集判定图是否连通，然后构造一个并查集，如果连通则其根相同，用数组b[]统计各个结点的连通度。

#include <string.h>
#include <stdio.h>
int f[1100],b[1100];
int find(int u)
{
	if (f[u]!=u)
		f[u]=find(f[u]);
	return f[u];
}
void merge(int u,int v)
{
	int t1=find(u),t2=find(v);
	if (t1!=t2)
		f[t2]=t1;
}
int main()
{
	int n,m,i,j,x,y;
	while(~scanf("%d",&n)&&n)
	{
		scanf("%d",&m);
		for (i=0; i<=1000; i++)
			f[i]=i;
		memset(b,0,sizeof(b));

		for (i=0; i<m; i++)
		{
			scanf("%d%d",&x,&y);
			b[x]++,b[y]++;
			merge(x,y);
		}
		int s=0,flag=0;
		for (i=1; i<=n; i++)
		{
		//	printf("<%d %d %d\n",i,f[i],b[i]);
			if (f[i]==i)
				s++;//如果有多个根节点，则不符合
			if (b[i]%2!=0)
				flag=1;//节点入度为偶数
		}
		if (s==1&&flag==0)
		printf("1\n");
		else
		printf("0\n");
	
	}
	return 0;
}

欧拉回路的判断(hdu1878)其一

原文：https://www.cnblogs.com/shidianshixuan/p/13729776.html