Count number of predecessors and successors of each vertex in a DAG

Problem: Given a DAG (V, E), count the number of  predecessors and successors of each vertex (excluding itself).

Complexity: O(N*N)

+ Firstly, we can use DFS to build the array isChild[u][v], where isChild[u][v] = true means v is child of u and otherwise. O(N*N)
+ Next, iterate all vertex pair (u, v) of DAG, if isChild[u][v] = true, then number of predecessors of v is increased 1 and number of successors of v is increased 1. O(N*N).


Happy coding