Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

shaaban_abdelrahim's blog

DAG to SCC
By shaaban_abdelrahim, 2 years ago, In English

I know that the minimum number of edges need to be add to a DAG to convert it to SCC (strongly connected component) is the max between the number of nodes having in-degree = 0 & the number of nodes having out-degree = 0. How to get these edges?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shaaban_abdelrahim (previous revision, new revision, compare).

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

You could loop through the nodes and check their degrees.

vector<int> source, sink;
for(int i = 0; i < n; ++i) {
    if(in[i] == 0) source.emplace_back(i);
    if(out[i] == 0) sink.emplace_back(i);
}

for(int u : sink) for(int v : source) add_edge(u, v);

You can speed this up if you create a fake node. After finding sources and sinks, add an edge from all sinks to the fake node and an edge from the fake node to all sources.

Here is how to speed it up.

vector<int> source, sink;
for(int i = 0; i < n; ++i) {
    if(in[i] == 0) source.emplace_back(i);
    if(out[i] == 0) sink.emplace_back(i);
}

int fake = ++n;
for(int u : sink) add_edge(u, fake);
for(int u : source) add_edge(fake, u);
→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Suppose there are $$$n$$$ weakly connected components $$$W_i$$$. From every $$$W_i$$$ pick vertices $$$v_i$$$ and $$$w_i$$$, such that $$$v_i$$$ has zero in-degree, $$$w_i$$$ has zero out-degree, and there is a path from $$$v_i$$$ to $$$w_i$$$ (they don't have to be distinct).

Add edges to complete the cycle $$$v_1w_1\ldots v_nw_nv_1$$$. For any remaining vertices $$$v$$$ with zero in-degree, add an edge $$$(v_1, v)$$$. For any remaining vertices $$$w$$$ with zero out-degree, add an edge $$$(w, v_1)$$$.

→ Reply