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?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | cry | 161 |
2 | awoo | 160 |
2 | maomao90 | 160 |
4 | atcoder_official | 157 |
5 | -is-this-fft- | 156 |
6 | nor | 155 |
7 | adamant | 153 |
8 | maroonrk | 152 |
8 | Um_nik | 152 |
10 | djm03178 | 146 |
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?
Name |
---|
Auto comment: topic has been updated by MuhammedShoeib (previous revision, new revision, compare).
You could loop through the nodes and check their degrees.
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.
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
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.
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)$$$.