Advertisement
serega1112

Number of vertices DFS

Mar 6th, 2021
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.40 KB | None | 0 0
  1.  
  2. n, s = map(int, input().split())
  3.  
  4. adj = []
  5. while n:
  6.     adj.append(list(map(int, input().split())))
  7.     n -= 1
  8.  
  9. s -= 1 # convert to zero-based
  10. st = [s]
  11. res = 0
  12. visited = [0] * len(adj)
  13. visited[s] = 1
  14.  
  15. while st:
  16.     cur = st.pop()
  17.     res += 1
  18.  
  19.     for v, edge in enumerate(adj[cur]):
  20.         if edge and not visited[v]:
  21.             st.append(v)
  22.             visited[v] = 1
  23.  
  24. print(res)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement