欧拉通路欧拉回路的判定 Hdu 1878 欧拉回路

矫情吗；* 2022-08-25 09:16 245阅读 0赞

欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路。

欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路。

无向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通；图中只有0个或2个度为奇数的节点

欧拉回路:图连通；图中所有节点度均为偶数

有向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通；除2个端点外其余节点入度=出度；1个端点入度比出度大1；一个端点入度比出度小1 或 所有节点入度等于出度

欧拉回路:图连通；所有节点入度等于出度

混合图（有的边是单向的，有的边是无向的。常被用于比喻城市里的交通网络，有的路是单行道，有的路是双行道。）

参考我的另一篇博文 [Poj 1637 Sightseeing tour (混合图的欧拉回路判定) ][Poj 1637 Sightseeing tour _]

**Hdu 1878 欧拉回路**

本题为无向图欧拉回路的判定

#include <cstdio>
    #include <cstring>
    
    const int N=1005;
    
    int father[N],degree[N];
    
    int find (int x)
    {
    	if (x==father[x])
    		return x;
    	return father[x]=find(father[x]);
    }
    
    int main ()
    {
    	int n,m,i;
    	while (scanf("%d",&n),n)
    	{
    		scanf("%d",&m);
    		for (i=1;i<=n;i++)
    			father[i]=i;
    		memset(degree,0,sizeof(degree));
    
    		while (m--)
    		{
    			int a,b;
    			scanf("%d%d",&a,&b);
    			father[find(b)]=find(a);
    			degree[a]++;
    			degree[b]++;
    		}
    		int p=father[1],flag=1;
    		for (i=1;i<=n;i++)
    			if (father[i]!=p || degree[i]&1)
    			{
    				flag=0;
    				break;
    			}
    		printf("%d\n",flag);
    	}
    	return 0;
    }

[Poj 1637 Sightseeing tour _]: http://blog.csdn.net/whyorwhnt/article/details/20701453