1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| from collections import deque
def BFS(graph,root,dis):
visit = set()
queue = deque([root])
visit.add(root)
while queue:
n = queue.popleft()
if n not in graph:
break
for i in graph[n]:
if i not in visit:
visit.add(i)
queue.append(i)
dis[i] = dis[n] +1
return dis
def solution(n, edge):
answer = 0
a = sorted([sorted(i) for i in edge])
b = sorted([sorted(i,reverse = True) for i in edge])
c = a+b
dicver = {}
for i in c:
if i[0] in dicver:
dicver[i[0]].append(i[1])
else:
dicver[i[0]] = [i[1]]
distance = dict.fromkeys(dicver.keys(),0)
result = BFS(dicver,1,distance)
answer = len([k for k,v in result.items() if max(result.values()) == v])
return answer
|