Advertisement
Okorosso

prettified modules

Jun 4th, 2021
777
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.07 KB | None | 0 0
  1. from typing import Dict, List
  2.  
  3.  
  4. def dfs(vertex: int, grapg: Dict[int, set], visited: List[bool]):
  5.     visited[vertex] = True
  6.     for near in grapg[vertex]:
  7.         if not visited[near]:
  8.             dfs(near, grapg, visited)
  9.  
  10.  
  11. with open("input.txt", "r") as f:
  12.     n, m = map(int, f.readline().split())
  13.     graph = {}
  14.  
  15.     for i in range(1, n + 1):
  16.         graph[i] = set({})
  17.  
  18.     line = list(map(int, f.readline().split()))
  19.     if m == 0:
  20.         pass
  21.     elif len(line) > 2:
  22.         for i in range(m):
  23.             graph[line[2 * i]].add(line[2 * i + 1])
  24.             graph[line[2 * i + 1]].add(line[2 * i])
  25.     else:
  26.         graph[line[0]].add(line[1])
  27.         graph[line[1]].add(line[0])
  28.         for i in range(m - 1):
  29.             leaf_1, leaf_2 = map(int, f.readline().split())
  30.             graph[leaf_1].add(leaf_2)
  31.             graph[leaf_2].add(leaf_1)
  32.  
  33. visited = [False] * (n + 1)
  34. count = 0
  35.  
  36. for i in range(1, n + 1):
  37.     if not visited[i]:
  38.         dfs(i, graph, visited)
  39.         count += 1
  40.  
  41. with open("output.txt", "w") as f:
  42.     f.write(str(count))
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement