Блог пользователя MuhammedShoeib

DAG to SCC
Автор MuhammedShoeib, 4 месяца назад, По-английски

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?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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);
→ Ответить
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.me/contest/22/problem/E

    → Ответить
    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)$$$.

→ Ответить