Advertisement
Nik_Perepelov

Егору прикол

Nov 3rd, 2021
698
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. import sys
  2.  
  3. sys.setrecursionlimit(100000)
  4.  
  5. num_v = int(input())
  6. num_e = int(input())
  7.  
  8. graph = []
  9. t_graph = []
  10.  
  11. used = [0] * num_v
  12. order = []
  13. component = []
  14.  
  15. pairs = []
  16.  
  17. for i in range(num_v):
  18.     graph.append([])
  19.     t_graph.append([])
  20.  
  21. for i in range(num_e):
  22.     edge = list(map(int, input().split()))
  23.     start_v = edge[0] - 1
  24.     end_v = edge[1] - 1
  25.  
  26.     pairs.append([start_v, end_v])
  27.     graph[start_v].append(end_v)
  28.     t_graph[end_v].append(start_v)
  29.  
  30.  
  31. def dfs_1(v=int):
  32.     used[v] = 1
  33.     for i in graph[v]:
  34.         if used[i] == 0:
  35.             dfs_1(i)
  36.     order.append(v)
  37.  
  38.  
  39. def dfs_2(v=int):
  40.     used[v] = 1
  41.     component.append(v)
  42.     for i in t_graph[v]:
  43.         if used[i] == 0:
  44.             dfs_2(i)
  45.  
  46.  
  47. for i in range(num_v):
  48.     if used[i] == 0:
  49.         dfs_1(i)
  50.  
  51. used = [0] * num_v
  52.  
  53. v_component = [0] * num_v
  54. n = 0
  55. for i in range(num_v):
  56.     v = order[num_v - 1 - i]
  57.     if used[v] == 0:
  58.         dfs_2(v)
  59.         for j in component:
  60.             v_component[j] = n
  61.         n += 1
  62.         component.clear()
  63.  
  64. b_stations = [0] * n
  65. for i in range(num_e):
  66.     if v_component[pairs[i][0]] != v_component[pairs[i][1]]:
  67.         b_stations[v_component[pairs[i][0]]] = 1
  68.  
  69. stations = []
  70. for i in range(n):
  71.     if b_stations[i] == 0:
  72.         for j in range(num_v):
  73.             if v_component[j] == i:
  74.                 stations.append(j + 1)
  75.                 break
  76.  
  77. print(len(stations))
  78. print(*stations, sep=' ')
  79.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement