hdu 1878 无向图的欧拉回路

时间:2021-03-03 16:04:47

原题链接 hdu1878

大致题意:

欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个无向图,问是否存在欧拉回路?

思路:

无向图存在欧拉回路的条件:1、图是连通的 2、所有点的度数为偶数

用邻接矩阵就可以搞了,dfs大法

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m; //n是节点数 m是边数
const int maxn=1000+5;
int G[maxn][maxn]; //邻接矩阵
int vis[maxn],res[maxn];

void dfs(int u)//判断连通性
{
    vis[u]=1;
    for(int i=1;i<=n;i++)
    {
        if(G[u][i]&&!vis[i]) dfs(i);
    }
}

int main(void)
{
    int x,y;
    while(scanf("%d",&n)==1&&n!=0)
    {
        scanf("%d",&m);
        memset(G,0,sizeof(G));
        memset(vis,0,sizeof(vis));
        memset(res,0,sizeof(res));
        for(int i=0;i<m;i++)
        {
        scanf("%d%d",&x,&y);
        G[x][y]=1;  G[y][x]=1; //边
        ++res[x]; ++res[y];
        }
        int ok=1;
        dfs(1);
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
            ok=0;
            break;
            }
        }
        if(ok)
        {
            for(int i=01;i<=n;i++)
            {
                if(res[i]%2==1) //存在奇点
                {
                    ok=0;
                    break;
                }
            }
        }
        if(ok)
        printf("1\n");
        else printf("0\n");
    }
    return 0;
}

ps:没怎么注意内存。。。。懒了

如果有不当之处欢迎指出!