MuhammedShoeib's blog

DAG to SCC
By MuhammedShoeib, 5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 months ago, # |
← 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
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but that code add (source.size() * sink.size()) edges, i need to add max(source.size(), sink.size()) edges only which is the min edges we can convert DAG to SCC, here is the problem i talk about https://codeforces.net/contest/22/problem/E

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you have a link you should mention it as part of the post. This is not just a DAG but a special case of DAG (it's a functional graph). There is an editorial for the problem available here. You can also go to the standings and check out the submissions.

      → Reply
»
5 months ago, # |
  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