Facebook

BFS safest cryptocurrency exchange

From minhhnh, 2 Weeks ago, written in Plain Text.
URL https://pastebin.pl/view/17870371
Embed
Download Paste or View Raw
Hits: 77
  1. from collections import defaultdict, deque
  2. from typing import List
  3.  
  4.  
  5. def build_graph(edges):
  6.     graph = defaultdict(list)
  7.     for edge in edges:
  8.         u, v = edge
  9.         graph[u].append(v)
  10.         graph[v].append(u)
  11.     return graph
  12.  
  13.  
  14. def bfs(graph, start):
  15.     visited = set()
  16.     queue = deque([(start, 0)])
  17.     map_level = defaultdict(int)
  18.     map_level[0] += 1
  19.     while queue:
  20.         node, level = queue.popleft()
  21.         print(node, level)
  22.         visited.add(node)
  23.         map_level[level] += 1
  24.         for neighbor in graph[node]:
  25.             if neighbor not in visited:
  26.                 queue.append((neighbor, level + 1))
  27.     return map_level
  28.  
  29.  
  30. n = int(input())
  31. edges = []
  32. for _ in range(n - 1):
  33.     u, v = map(int, input().split())
  34.     edges.append([u, v])
  35. target_level = int(input())
  36.  
  37. graph = build_graph(edges)
  38. map_level = bfs(graph, 1)
  39. print(map_level[target_level - 1])
  40.  

Reply to "BFS"