# What happens if you run Kosaraju’s algorithm on a DAG?

What happens if you run Kosaraju’s algorithm for finding strongly connected components of directed graphs on a DAG?

• What do you think of it? What is your specific question? – hengxin May 29 '17 at 7:54
• Try it and see what happens! – Yuval Filmus May 29 '17 at 10:30

A directed graph $$G(V, E)$$ is acyclic if and only if $$G$$ has no SCCs with more that one vertex. Because a directed cycle is SCC by definition of the cycle.
Hence, the result of the Kosaraju’s algorithm on a DAG will return $$|V|$$ trivial SCCs. In other words, it returns $$\{\{v\}\mid v\in V\}$$.