The adjacency matrix is an n × n matrix of 0's and 1's,
where n is the number of vertices in the graph.
Matrix entry (i, j) is 1 if an edge
connects vertices i and j in the graph.
Since neither interval [6,9] and [2,4] is contained in the
other, one cannot be an ancestor of the other. In fact, since
there's just one number 5 between v's post number and
u's pre number, it must be that
v's parent in the tree must be a sibling of
u. (If you prefer, u must be v's
aunt or uncle.)
A tree edge is one that is traversed in the course of
performing the recursion.
A back edge is one that is ignored because its
destination is an ancestor of the source vertex.
A cross edge is one that is ignored because its
destination was visited prior to visiting the source vertex, but
the destination is not an ancestor of the source vertex.
A forward edge is one that is ignored because its
destination was previously visited in the course of visiting the source
vertex's other neighbors.
A dag is a directed acyclic graph. That is, it is a directed graph
that contains no cycles.
Any combination of the six letters is OK, as long as CFED appears as a
subsequence and B appears before both A and E. One solution is CBAFED.
There are 18. In each ordering, A, B, E, and F must precede
C, with A before B and E before F. Either A will come first or E
will come first.
If A comes first, then B must be either before E, between E and F, or after F.
If E comes first, then F must be either before A, between A and B, or after B.
Thus, there are 6 ways to order these four vertices; and after
those four vertices will be C.
We must also place D, G, and H after C. G must precede H, but
D might come before G, between G and H, or after H, for a total of
three configurations for each of the six possible orderings of A/B/E/F.
Thus the total number of orderings is 3 ⋅ 6
Create an empty linked list, and then perform a depth-first search on
the dag. At the end of the recursive function
add the explored node at the front of the linked list. Following
completion of the depth-first search, the linked list will
contain the vertices in topological order.
O(m ⋅ n).
There are n iterations of the outer loop,
and over all iterations of the outer loop, there are
2 m iterations of the inner loop over
(There are 2 m iterations because if I go through each
vertex and check each edge around it, then I'll end up checking
each edge once for each of its two endpoints.)
For each iteration of the loop over
b, there are at most
n iterations of the loop over
iteration taking O(1) time. Thus each iteration of
b loop takes O(n) time.
Over all 2 m iterations of the
overall, the time spent is
O(m ⋅ n).
The outer loop over
i takes just O(1)
time per iteration, if we neglect the time spent on the
b loop. Thus the outer loop takes
O(n) time over all iterations, neglecting
the time on the
b loop. The code outside the outer
loop takes O(1) time.
Thus the total time is
O(1 + n + m ⋅ n),
O(m ⋅ n).