Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- sys.setrecursionlimit(100000)
- num_v = int(input())
- num_e = int(input())
- graph = []
- t_graph = []
- used = [0] * num_v
- order = []
- component = []
- pairs = []
- for i in range(num_v):
- graph.append([])
- t_graph.append([])
- for i in range(num_e):
- edge = list(map(int, input().split()))
- start_v = edge[0] - 1
- end_v = edge[1] - 1
- pairs.append([start_v, end_v])
- graph[start_v].append(end_v)
- t_graph[end_v].append(start_v)
- def dfs_1(v=int):
- used[v] = 1
- for i in graph[v]:
- if used[i] == 0:
- dfs_1(i)
- order.append(v)
- def dfs_2(v=int):
- used[v] = 1
- component.append(v)
- for i in t_graph[v]:
- if used[i] == 0:
- dfs_2(i)
- for i in range(num_v):
- if used[i] == 0:
- dfs_1(i)
- used = [0] * num_v
- v_component = [0] * num_v
- n = 0
- for i in range(num_v):
- v = order[num_v - 1 - i]
- if used[v] == 0:
- dfs_2(v)
- for j in component:
- v_component[j] = n
- n += 1
- component.clear()
- b_stations = [0] * n
- for i in range(num_e):
- if v_component[pairs[i][0]] != v_component[pairs[i][1]]:
- b_stations[v_component[pairs[i][0]]] = 1
- stations = []
- for i in range(n):
- if b_stations[i] == 0:
- for j in range(num_v):
- if v_component[j] == i:
- stations.append(j + 1)
- break
- print(len(stations))
- print(*stations, sep=' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement