首页 > 其他 > 详细

Even Tree

时间:2015-05-18 12:40:01      阅读:226      评论:0      收藏:0      [点我收藏+]

Link:

  https://www.hackerrank.com/challenges/even-tree

 1 def search(a,b): # 根据核心算法和题目要求要筛选边
 2     seen = {}
 3     seen[a] = True
 4     q = []
 5 
 6     for x in adj[a]:
 7         if x != b:
 8             seen[x] = True
 9             q.append(x)
10     s = len(q) + 1
11     while q:
12         n = q.pop()
13         for x in adj[n]:
14             if x not in seen:
15                 seen[x] = True
16                 q.append(x)
17                 s += 1
18     return (s+1)%2
19 
20 [N,M] = [int(x) for x in raw_input().split( )]
21 edges = [] # 保存边的list
22 adj = {} # 保存邻接的dict
23 for a in xrange(1,N+1): # 初始化
24     adj[a] = []
25 
26 for a in xrange(M):
27     [x,y] = [int(z) for z in raw_input().split( )]
28     adj[x].append(y) # 保存边的对应,没有方向性
29     adj[y].append(x)
30     edges.append((x,y)) # 保存边边
31 
32 count = 0
33 for e in edges:
34     (x,y) = e
35     if search(x,y): #依次查看每个边是否能移开
36         count += 1
37         adj[x].remove(y)
38         adj[y].remove(x)
39 
40 print count

学习

  图的基本结构

    edge, adj建立dict/list保存

  然后根据算法进行计算

 

  本质

    换了一个数据的结构

Even Tree

原文:http://www.cnblogs.com/sangocare/p/4511352.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!