In the graph theory, is a strongly connected component SCC form a DAG?

Question

I was trying to solve a problem to design an algorithm to determine whether a direct graph is semi-connected. Someone says it can be done by using topological sort every SCC in the graph. And SCC is guaranteed to be DAG. However, I think SCC graph must be a circle, why it is a DAG since DAG mean no circle.

Answer 1

You misunderstood the argument.

Suppose you have a graph that has points

A1 <--> A2 <--> A3 --> B1 <--> B2 --> C1 <--> C2

and A1 A2 A3, B1 B2, C1, C2 are SCC.

Then you treat A1 A2 A3 as a single point A. Any node connecting to one of A1 A2 A3 is treated as connecting to A, Any node connected from one of A1 A2 A3 is treated as connected from A. Same for merging points to B, C

So it became A --> B --> C. It is guaranteed that this is a DAG.