Today we look at another example of decrease and conquer algorithm. This is the topological sort and we will cover it in two posts. This algorithm is based on depth first search. The Topological Sort works on a directed graph. Directed graph is one where you can traverse the vertices in one direction but not the other. As usual we represent these with adjacency matrix. Bidirectional transfer will have explicit edges for both directions. A directed edge from u to V will have exit number of v less than than u. We justify this claim with the following two cases.  In the first case let's say v was unmarked when dfs explores v. Here v comes off the stack first so its exit number is smaller than that of u. In The Second Case, the depth first search visits a marked vertex v. In this case v is already off the stack and finished. Its exit number will be less than that of u.
This gives us a dfs based algorithm for topological sort.
we run DFS(G) and compute exit numbers.
If DFS(G) discovers a back edge, then G is not a directed graph, so we report this as an error and exit.
We list the vertices in decreasing order of exit number.  This gives us the entry as the root vertex and the last vertex at the end.
The worst case complexity of this DFS based algorithm for topological sort  is based on
DFS + Sorting
The DFS takes O(n^2) as adjacency matrix and O(n+m) as adjacency list.
The sorting takes O(nlogn) and we list the vertices as generated reverse list. So we don't really need to sort but we just need to reverse the list.
We now look at a decrease and conquer algorithm.
The source vertex has no incoming edges.
Every diag has a source vertex. A source vertex is one that has no incoming edges.  If there is a cycle , then it is no longer a diag.
So we can enumerate the source vertex first.
Then we remove the source vertex and this implies we should still be left with a diag. This gives us the construct for a decrease and conquer algorithm. We write it this way:

while graph is not empty {
identify source vertex v
append v to topologically sorted list
remove v from G
}

We do this by computing the indegree of each vertex.
first we set this to zero for all vertices.
Then we increment by 1 for all edges to an inbound vertex.
then we identify the source vertex where the indegree is zero and append v to queue.

while (queue is not empty)
{
v is set to head of queue; we enumerate v; delete head of queue;
for each (v, w) in E // as many outbound edges
{
 indegree[w] = indegree[w] - 1;
if (indegree[w] == 0) { append w to queue; }
}
}

Notice that initialization steps takes O(n) and O(m).
The while loop takes O(n) while the for loop take O(deg(V)) time
If we use adjacency list, the complexity is comes to O(n+m) where we decrease the complexity from O(n^2) in adjacency matrix because we just reverse the list.
This topological sorting has a practical application in scheduling tasks while respecting dependencies and we have seen two different algorithms for it.