题目描述:
在一个景区,没有人愿意重复走过同一条路,因此必须要修建一条浏览路径,使得游客可以走过所有的道路且不会重复通过某一条路,同时游览过所有的景点,景点可以重复经过,游览道路的起点和终点你可以自行设计。
已知景区共有n个景点已经有了m条道路,为了节约成本,你需要修建尽可能少的道路使得存在一条如题所述的游览路径。
输入:
第一行包含两个整数n,m代表n个景点和m条道路(1<=n,m<=100000),
景点编号1-n
接下来有m行,每行两个正整数u,v,表示在景点u和景点v之间有一条路,注意,在u和v之间可能有多条不同的道路存在,这些道路都需要经过。
样例输入
3 3
1 2
1 3
2 3
样例输出:
0
n位度为奇数的景点个数
res = max((n-2)/2,0)
n, m = [int(i) for i in input().split(' ')]
save = []
for i in range(m):
save.append([int(j) for j in input().split(' ')])
d = {}
for j in save:
for k in j:
if k not in d:
d[k] = 1
else:
d[k] += 1
count = 0
for i in d:
if d[i] % 2 != 0:
count += 1
res = (count - 2) // 2
print(max(res, 0))