# Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n)

I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author claimed that this can be done in $$O(n)$$.

How should I understand this time complexity? Just because we traverse all nodes in $$O(n)$$? But in the iteration for some node $$v$$, one also needs to traverse all its incident edges. Does that mean the time complexity should be $$O(m+n)$$ or $$O(m)$$? Is it related to the data structure which one uses to represent the DAG?

• In all common implementations of a graph, you will have direct access to in and out-degree of a node, so you don't need to traverse the edges individually. But even if you don't, you can augment your data structure s.t. you add/update in/out-degrees while you're constructing the graph. – Ameer Jewdaki Nov 28 '19 at 11:42

We will use a data structure that I am going to call the characteristic-hash-vector (CHV). Given a graph $$G$$ of size $$n$$, and a subgraph $$S \subseteq G$$, the characteristic vector $$X_S$$ is the vector of size $$n$$ that has a 1 for each node in $$S$$ and a 0 for all other elements. The CHV is a way of representing the characteristic vector using a hashmap. Given a subset $$S$$, each node $$v$$ in $$G$$ is mapped to $$X_S(v)$$.
Let's try representing the DAG as a set of nodes, and with each node $$x$$, maintain a CHV for incoming nodes $$y$$ (there exists a directed edge from $$y$$ to $$x$$) and a CHV for outgoing nodes $$w$$ (there exists a directed edge from $$x$$ to $$w$$). Then, it is easy to find a node with no incoming edges. Start with any arbitrary node, and then pick any arbitrary node from its incoming CHV, and so on, until we reach a node with an empty incoming CHV. By the proof the earlier in the section, we know that this search will terminate in $$O(n)$$ time.
Then, we go to each node in this final node's outgoing CHV, and remove the final node from its incoming CHV (this is where we use the constant-time properties of hashmaps/CHVs). This process also takes $$O(n)$$ time.
Thus, we have a runtime of $$O(n)$$ for each iteration of the loop in the algorithm to compute a topological order for a DAG.