欧拉回路

[编程题]欧拉回路

热度指数：6772 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

输出

1
0

算法知识视频讲解

Python

songofjoy

python为什么会报错呢？加 try exception就通过了，不加就报错
while True:
N, M = map(int, input().split())
if N == 0:
break
values = dict()
for i in range(M):
a, b = map(int, input().split())
if a not in values:
values[a] = 0
if b not in values:
values[b] = 0
values[a] += 1
values[b] += 1
euler = True
for k, v in values.items():
if v % 2 != 0:
euler = False
print(1 if euler else 0)

发表于 2020-09-22 19:48:09 回复(1)

Python

TimeMac

判断各个节点的度是否为偶数，自环增加度为2，不影响，所以可以加上去

while True:
    try:
        n,m = list(map(int, input().split()))
        if n == 0:
            break
        nodes = [0 for i in range(n+1)]
        for i in range(m):
            temp = list(map(int, input().split()))
            nodes[temp[0]] += 1
            nodes[temp[1]] += 1
        whetherEuler = True
        for i in range(1,n+1):
            if nodes[i] % 2 == 1:
                whetherEuler = False
                break
        if whetherEuler:
            print(1)
        else:
            print(0)
    except Exception:
        break

编辑于 2018-09-28 16:36:25 回复(0)