Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- n, m = map(int, input().split(' '))
- graph = {}
- pairs = []
- for _ in range(m):
- x, y = map(int, input().split(' '))
- pairs.append((x, y))
- graph.setdefault(x, [])
- graph.setdefault(y, [])
- graph[x].append(y)
- graph[y].append(x)
- subtree = [1] * (n + 1)
- visited = [False] * (n + 1)
- def dfs(node):
- if not visited[node]:
- visited[node] = True
- for out in graph[node]:
- if not visited[out]:
- dfs(out)
- subtree[node] += subtree[out]
- dfs(1)
- for x, y in pairs:
- small_subtree = min(subtree[x], subtree[y])
- print("Crossing edge {}-{} there are {} paths".format(x, y, small_subtree * (n - small_subtree)))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement