原题链接 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:没怎么注意内存。。。。懒了
如果有不当之处欢迎指出!