DAG to SCC

Revision en2, by faresbasbas, 2020-07-23 02:26:49

Recently I've read about minimum number of needed edges to construct SCC from a DAG. And it was the MAX(x,y) where x is the number vertices with 0 in-degree and y is the number of vertices with 0 out-degree. But i am wondering how to find such combination of edges in O(N) time. Thanks in advance :)

edit : solved. thank you very much for all people who helped me :)

Tags #graph theory, graph algorithm, bipartite matching, matchings

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English faresbasbas 2020-07-23 02:26:49 68
en1 English faresbasbas 2020-07-21 05:07:23 311 Initial revision (published)