Counting incoming edges in a directed acyclic graph

0
votes

Given a directed acyclic graph (DAG), is there an algorithm that runs in linear time that counts the in-degree of each vertex (and the source of that edge), given that we know a root node (a node that from it you can reach every other vertex)?

1
algorithmdirected-acyclic-graphs
What is your input? Adjacency lists? Are your nodes identified by integers 1 to n or 0 to n - 1? In that case yes, you just walk through all edges and increment a counter in an array. - Niklas B.
Actually, my graph is the SCC graph of an original graph. The nodes are not identified by integers. They are represented as adjacency lists, and I have a topological ordering of the SCC graph - TheNotMe
Define linear time - linear in number of edges or number of vertices, or both? - Bernhard Barker
Both. $O(|V|+|E|)$ is my aim. - TheNotMe
And I wish the downvoter would first state what is wrong with my question. - TheNotMe

1 Answers

1
votes

Let's assume your nodes are numbered from 1 to n. There's a simple solution: Create an array D of size n, with values initialized to 0. Then walk through all edges (v, w) and increment D[w] by one. In the end D[w] will be the in-degree of vertex w.