CareerCup

<pre lang="" line="1" title="CodeMonkey6195" class="run-this">// this must be a directed graph

// a global vector to record the visited Nodes
Vector visited;

vector<Node> DFSFind (Node me, Stack<Node> myAncestors) {
// add myself as my ancestor
myAncestors(me);
visited(me);

// init my descendents
Vector<Node> myDescendents;

for (Edges e : me.outEdges) {
if (myAncestors.contains(e.tail)) {
// this is a reverse edge -> including self-reverse
}
else if (myDescendents.contains(e.tail)) {
// this is a forward edgs
}
else if (visited.contains(e.tail)) {
// since this node is visited but neither my ancestor or my descendent -> a cross edge
}
else {
myDescendents UNION DFSFind(e.tail, myAncestors);
}
}

return myDescendents;
}
</pre><pre title="CodeMonkey6195" input="yes">Note that the "forward," "reverse," and the "cross edges" are defined on a Depth First Search. So different DFS will result in different set of these edges.
So, based on a DFS,
on a given a node and one of its outer edge:
1. if the edge connects to one of its ancestor -> a reverse edge (beware of the self-reverse)
2. if the edge connects to one of the "KNOWN" descendent -> a forward edge
3. if this edge connects to neither an ancestor or a descendent but a visited node -> a cross edge

This is my opinion....
Please correct me if there is any error.

Thanks.</pre>

"Note that the "forward," "reverse," and the "cross edges" are defined on a Depth First Search. "

Why they are pretty much defined for BFS as well..