# Determining whether DAG is semi-connected

I have been asked to write an algorithm which determine whether a DAG is semi-connected. (Recall that a DAG is semi-connected if for any pair of vertices $$x,y$$, there is either a path from $$x$$ to $$y$$ or a path from $$y$$ to $$x$$.)

My idea that that a DAG is semi-connected iff it has a unique topological sort. Therefore, I can use a topological sorting algorithm, checking each time that there is a unique candidate for the next vertex in the topological order.

Does my idea work?

• Is this idea correct? If you can show that the algorithm works, then it is correct. Oct 17 at 9:08
• I do not think your idea is correct. Consider a directed graph with two vertices and no edges. I claim that this graph is a DAG which does not have a unique topological ordering.
– Bob
Oct 17 at 18:03