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

**Complexity:** O(N*N)

**Algorithm:
**+ 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).

**Code: **https://goo.gl/4aHccl

Happy coding

Advertisements