Maximum SCC size in a directed graph if one new edge can be added.

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
39:37:55
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Maximum SCC size in a directed graph if one new edge can be added.

Автор r3novatio, история, 3 года назад, По-английски

I came across this problem in which you have been given a directed graph $$$G=(V,E)$$$ with $$$|V|,|E|\leq 10^5$$$ and one additional edge can be added to $$$E$$$. What can be the maximum size of a strongly connected component in the resulting graph?

If anyone knows an approach, do share.

Thanks.

EDIT: I apologize that the $$$O(V.(V+E))$$$ algorithm that I thought would solve this also turned out to be incorrect.

#graphs, #graph theory, directed graph, strongly connected, #scc

r3novatio
3 года назад
34

Комментарии (34)

Написать комментарий?

sheaf

3 года назад, # |

← Rev. 3 →

deleted.

→ Ответить

r3novatio

3 года назад, # ^ |

← Rev. 2 →

+25

Consider such a case. The maximum sum path would suggest 1+5+3. But the actual answer here is 10 (by joining sink SCC of left diamond to its source SCC, we get 1+2+3+4 in one SCC)

→ Ответить

Redux

3 года назад, # ^ |

The image isn't loading for me. Can you try again or give input in text form?

→ Ответить

r3novatio

3 года назад, # ^ |

Yeah, my bad. Check now

→ Ответить

idontknowthesestuff

3 года назад, # |

-7

First create a condensation graph, it will be a DAG(with multiple sources and sinks)

in condensation graph make sure to store number of nodes(original graph) for each node(SCC or dag's node)

for every sink calculate the number of nodes and from which source you achieved the max nodes( this can be done using simple graph dp)

connect the sink to the source(you stored), this should give the required graph. This can be achieved in O(V+E) as only dfs is used here couple of times

→ Ответить

r3novatio

3 года назад, # ^ |

This is what I thought of. Unfortunately it has a worst case of $$$O(V(V+E))$$$ because you might need to traverse a significant portion of graph in every dfs call (due to overlapping) and the dfs will be called for as many sinks there can be (which can be $$$O(V)$$$)

→ Ответить

idontknowthesestuff

3 года назад, # ^ |

← Rev. 2 →

-8

You don't have to do dfs for every sink you can find max number of nodes in every sink in single dfs

first do a topological sort on condensation graph

go in order and perform dfs and when you return from a recursion store the maximum number of nodes from the child nodes( here you will visit every node every time)

something like this

number_of_nodes[source] = number_of_nodes_in_scc[source]
max_number_nodes_of_child = 0
for every child :
     dfs(child)
     max_number_nodes_of_child = max(max_number_nodes_of_child,number_of_nodes[child])
number_of_nodes[source] += max_number_nodes_of_child

EDIT : Here is a problem which uses the same idea

→ Ответить

r3novatio

3 года назад, # ^ |

+11

What you have achieved will be the maximum sum path of the condensed graph. Look at the case above (in the image). This algorithm will only find one path with maximum nodes sum. It would fail on the case with a diamond because it'll only output the sum achieved through heaviest path.

→ Ответить

idontknowthesestuff

3 года назад, # ^ |

yep I was wrong, please update this blog if you get some better solution from different source

→ Ответить

Redux

3 года назад, # |

What is the problem source?

→ Ответить

zeus0106

3 года назад, # ^ |

Codenation Innovation Labs Placement Test

→ Ответить

_yui_

3 года назад, # |

Best I could think of was an O(V(V+E)) approach.

Share it please.

→ Ответить

r3novatio

3 года назад, # ^ |

Make a metagraph $$$G'$$$ where each node has a value equal to the size of SCC it represents. Let $$$ans= -inf$$$

For every source $$$s$$$ in $$$G'$$$ do,

initialise a dp table and run $$$dfs(s)$$$ to fill the table by (i) $$$table[s]=value[s]$$$ and then (ii) propogating $$$table[s]$$$ value to $$$table[v]$$$ for each (visited or unvisited) neighbour $$$v$$$ of $$$s$$$.
If maximum value of $$$table[t]$$$ for sink (of this dfs call) $$$t$$$. Then $$$ans=max(ans,table[t])$$$
Clear the dp table/visited array and go to next source (step 1)

→ Ответить

_yui_

3 года назад, # ^ |

+13

As I understand from your comment, you fix source $$$s$$$, than run some $$$dfs$$$ to calculate $$$table[t]$$$ for all $$$t$$$, and than claim that after your calculations $$$table[t] = \sum_{v} value[v]\cdot f(s,v)\cdot f(v,t)$$$, where $$$f(u,v) = 1$$$ if $$$v$$$ is reachable from $$$u$$$, else $$$0$$$. I cant get how your first step calculates this sum, what do you mean by propagating something to children? Need some formal explanations.

→ Ответить

r3novatio

3 года назад, # ^ |

Yes, I realised this algorithm wouldn't hold up. While propogating values to the descendants, we might run into duplicacies in case where the descendants later happen to lead to common nodes. Sorry but my $$$O(V.(V+E))$$$ algorithm is incorrect.

→ Ответить

okwedook

3 года назад, # |

+26

This looks unsolvable, because solving this is as hard as telling the number of reachable nodes for each node in a DAG, which is a known problem and only has approximations in sub-quadratic time. Correct me, if I'm wrong.

→ Ответить

babyBay

3 года назад, # ^ |

← Rev. 2 →

[Deleted]it wont work , I misread the ques.

→ Ответить

Mr.Doap

3 года назад, # ^ |

Cant we find out the number of reachable nodes by iterating through the nodes in the reverse order of topological sorted order and say that dp[u]+=dp[v] for every (u,v) edge.Since this is a DAG I think this way the number of reachble nodes can be counted. Please correct me If I am wrong

→ Ответить

Rezwan.Arefin01

3 года назад, # ^ |

+20

This will over count whenever some path starting from two childs of u overlap. For example:

You'll have $$$dp(3) = 3$$$ and $$$dp(2) = 3$$$, but $$$dp(1)$$$ is not $$$3+3$$$.

→ Ответить

r3novatio

3 года назад, # ^ |

→ Ответить

-is-this-fft-

3 года назад, # ^ |

+15

Is it really from some hiring test? Writing "atmost" and "<=" seems so unprofessional. (Also the word order is very strange in "Find the maximum size...")

→ Ответить

okwedook

3 года назад, # ^ |

I like "find the maximize size" even more:)

→ Ответить

valhala7

3 года назад, # ^ |

-8

Professional or not , but people will always judge you. So you only solve problems which are written professionally? Sorry not everyone is pro as you. They made mistakes that's why they are called as humans.

→ Ответить

-is-this-fft-

3 года назад, # ^ |

← Rev. 3 →

What exactly is the point of this comment? How are "being pro as me" or "people will always judge you" even related to all this? And I have not said I wouldn't solve problems like this, but I'd certainly form a certain opinion about this company or agency.

I would also like to point out that my original comment wasn't even really a criticism. I was just expressing my shock — I found it totally unbelievable that a professional could write like this. You are unreasonably defensive for some reason.

People make mistakes, it's more about being able to prevent mistakes. Hiring an editor or even just proofreading, for example.

→ Ответить

valhala7

3 года назад, # ^ |

Nowadays it feels like GrammerForces ,before asking for help you have to think a lot whether you should ask or not because some pro Coder will comment about their English or say how they should ask for help. Feels like I am in University where I have to think what others will say If ask this doubt. I comment something and it triggered you, then you suggest something for the solution. I understand it's the author's mistake. " I found totally unbelievable that a professional could write like this " . Awww Do I have to prepare a list of CF unrated rounds happened because of author's solution issues?

Sorry for my poor english. I just want to say keep it simple and sweet . Do codeforces not grammar or englishforces. Sorry for bothering you. GLHF

→ Ответить

tfg

3 года назад, # ^ |

You can take 1 minute to fix your comment

Like this

Btw the only real word I changed was GrammerForces to GrammarForces but as I can see in the last line you can write grammar properly if you try (and that typo could have been on purpose, idk). There are some other issues with the choice of past/present and maybe one letter wrong here and there but those aren't as important as proper punctuation and spacing.

→ Ответить

_yui_

3 года назад, # ^ |

Why did you even write this? The problem here is that author`s solution is some unproven shit, and as I understand nobody can propose solution for a given problem even in $$$\mathcal{o}(n^3)$$$. So yes, problemsetter is unprofessional.

→ Ответить

okwedook

3 года назад, # ^ |

+12

Even though I don't care about the markup, which might be unavailable to technical difficulties, there is a huge problem in grammatical errors, cause they lead to misunderstanding and are as said "unprofessional". Just imagine seeing such a text in your workflow. Also the solution (even close to reality, which works with good probability) remains unknown, so I would love to see the official editorial, cause the author is either a genius or his solution is completely wrong.

→ Ответить

-is-this-fft-

3 года назад, # ^ |

Do you have a reduction? (I also think this problem is unsolvable, but I can't really show it either).

Also, did you mean to write "at least as hard as" or really "as hard as"? If it is as hard as counting reachable nodes, we could have a fast solution with "bit-parallelism".

→ Ответить