首页 > ACM题库 > 九度OJ > 九度-1027-欧拉回路[解题代码]
2013
12-12

九度-1027-欧拉回路[解题代码]

题目来源:2008年浙江大学计算机及软件工程研究生机试真题

题目描述:
    欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?
输入:
    测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 < N < 1000 )和边数M;随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号)。当N为0时输入结束。
输出:
    每个测试用例的输出占一行,若欧拉回路存在则输出1,否则输出0。
样例输入:
3 3
1 2
1 3
2 3
3 2
1 2
2 3
0
样例输出:
1
0

cpp 代码如下:
#include <stdio.h>
#include <string.h>
int du[1000];
int main()
{
    int n, m;
    int u, v;
    int i;
    while(scanf("%d", &n) && n != 0)
    {
        memset(du, 0, sizeof(du));
        scanf("%d", &m);
        while(m--)
        {
            scanf("%d %d", &u, &v);
            du[u]++;
            du[v]++;
        }
        for(i = 1; i <= n; i++)
        {
            if(du[i]&1) break;
        }
        if(i == n+1) puts("1");
        else puts("0");
    }
    return 0;
}
/**************************************************************
	Problem: 1027
	User: coder
	Language: C
	Result: Accepted
	Time:40 ms
	Memory:916 kb
****************************************************************/


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。