Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from typing import Dict, List
- def dfs(vertex: int, grapg: Dict[int, set], visited: List[bool]):
- visited[vertex] = True
- for near in grapg[vertex]:
- if not visited[near]:
- dfs(near, grapg, visited)
- with open("input.txt", "r") as f:
- n, m = map(int, f.readline().split())
- graph = {}
- for i in range(1, n + 1):
- graph[i] = set({})
- line = list(map(int, f.readline().split()))
- if m == 0:
- pass
- elif len(line) > 2:
- for i in range(m):
- graph[line[2 * i]].add(line[2 * i + 1])
- graph[line[2 * i + 1]].add(line[2 * i])
- else:
- graph[line[0]].add(line[1])
- graph[line[1]].add(line[0])
- for i in range(m - 1):
- leaf_1, leaf_2 = map(int, f.readline().split())
- graph[leaf_1].add(leaf_2)
- graph[leaf_2].add(leaf_1)
- visited = [False] * (n + 1)
- count = 0
- for i in range(1, n + 1):
- if not visited[i]:
- dfs(i, graph, visited)
- count += 1
- with open("output.txt", "w") as f:
- f.write(str(count))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement