游客 注册 | 登录
中文 | En

1643 - 欧拉回路

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

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

题目输入

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N <= 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结束。

题目输出

每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

输入/输出样例

输入格式

3 3
2 3
1 2
1 3
3 2
1 2
2 3
0

输出格式

1
0

C语言解答

#include<stdio.h>
int main()
{
  int n,m,a[1000]={0},i,temp,b,c,count;
  while(scanf("%d %d",&n,&m)!=EOF&&n!=0)
    {
      temp=m;count=0;
      while(m--)
      {
        scanf("%d %d",&b,&c);
        a[b]++;a[c]++;
      }
      for(i=1;i<=temp*2;i++)
       {
        if(a[i]%2!=0){count=1;break;}
       }
       if(count==0)printf("1\n");
       else printf("0\n");
       for(i=0;i<n;i++)
       a[i]=0;
    }
  return 0;
}

C++解答

#include <cstdio>
#include <vector>
#include <cstring>

const int N = 1005;

std::vector < int > v[N];
bool vis[N];

void dfs(int x) {
    vis[x] = true;
    for (std::vector < int >::iterator it = v[x].begin(); it != v[x].end(); ++it)
        if (!vis[*it])
            dfs(*it);
}

int main() {
    int n, m;
    while (scanf("%d", &n) && n > 0) {
        scanf("%d", &m);
        for (int i = 0; i < N; ++i)
            v[i].clear();
        while (m--) {
            int x, y;
            scanf("%d %d", &x, &y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        memset(vis, 0, sizeof(vis));
        dfs(1);
        int ans = 1;
        for (int i = 1; i <= n; ++i) {
            if (v[i].size() % 2 == 1)
                ans = 0;
            if (!vis[i])
                ans = 0;
        }
        printf("%d\n", ans);
    }
    return 0;
}
请先登陆