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?

  • $\begingroup$ Is this idea correct? If you can show that the algorithm works, then it is correct. $\endgroup$ Oct 17 at 9:08
  • $\begingroup$ 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. $\endgroup$
    – Bob
    Oct 17 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.