Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. // The problem states it wants the vertex on which the graph is accessible, and if not, return any vertex.
  2. // This can be trivial since you can return the first item in the topological ordering and always be correct.
  3. // However, if we are required to return true or false, then we must perform this funciton.
  4. //
  5. // G: directed acyclic graph
  6. // T: topological ordering of G
  7. getAccessible(G, T):
  8. lastVisited = stack()
  9. lookBack = set()
  10. for v in T:
  11. repeat = true
  12. while repeat:
  13. if v == T[0]:
  14. lastVisited.push(v)
  15. repeat = false
  16. else if lastVisited.empty()
  17. return v // G is not accessible, I can return T[0] and be correct according to the problem
  18. else if lastVisited.peek() -> v exists in G:
  19. lastVisited.push(v)
  20. repeat = false
  21. for u in lookBack:
  22. if u -> v exists in G:
  23. lastVisited.push(v)
  24. repeat = false
  25. break
  26. if repeat == true: // none of the vertices in lookBack or lastVisited.peek() lead to v
  27. lookBack.add(lastVisited.pop())
  28. // if G is accessible, then lastVisited will be non-empty
  29. return T[0] // again, I can return T[0] and be correct
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement