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)

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s