Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // The problem states it wants the vertex on which the graph is accessible, and if not, return any vertex.
- // This can be trivial since you can return the first item in the topological ordering and always be correct.
- // However, if we are required to return true or false, then we must perform this funciton.
- //
- // G: directed acyclic graph
- // T: topological ordering of G
- getAccessible(G, T):
- lastVisited = stack()
- lookBack = set()
- for v in T:
- repeat = true
- while repeat:
- if v == T[0]:
- lastVisited.push(v)
- repeat = false
- else if lastVisited.empty()
- return v // G is not accessible, I can return T[0] and be correct according to the problem
- else if lastVisited.peek() -> v exists in G:
- lastVisited.push(v)
- repeat = false
- for u in lookBack:
- if u -> v exists in G:
- lastVisited.push(v)
- repeat = false
- break
- if repeat == true: // none of the vertices in lookBack or lastVisited.peek() lead to v
- lookBack.add(lastVisited.pop())
- // if G is accessible, then lastVisited will be non-empty
- return T[0] // again, I can return T[0] and be correct
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement