### r3novatio's blog

By r3novatio, history, 8 months ago,

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.

• +39

 » 8 months ago, # | ← Rev. 3 →   0 deleted.
•  » » 8 months ago, # ^ | ← 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)
•  » » » 8 months ago, # ^ |   0 The image isn't loading for me. Can you try again or give input in text form?
•  » » » » 8 months ago, # ^ |   0 Yeah, my bad. Check now
 » 8 months ago, # |   -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
•  » » 8 months ago, # ^ |   0 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)$)
•  » » » 8 months ago, # ^ | ← 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 dfsfirst do a topological sort on condensation graphgo 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
•  » » » » 8 months ago, # ^ |   +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.
•  » » » » » 8 months ago, # ^ |   +9 yep I was wrong, please update this blog if you get some better solution from different source
 » 8 months ago, # |   +3 What is the problem source?
•  » » 8 months ago, # ^ |   +3 Codenation Innovation Labs Placement Test
 » 8 months ago, # |   0 Best I could think of was an O(V(V+E)) approach.Share it please.
•  » » 8 months ago, # ^ |   +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)
•  » » » 8 months ago, # ^ |   +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.
•  » » » » 8 months ago, # ^ |   0 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.
 » 8 months ago, # |   +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.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +3 [Deleted]it wont work , I misread the ques.
•  » » 8 months ago, # ^ |   0 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
•  » » » 8 months ago, # ^ |   +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$.
•  » » 8 months ago, # ^ |   0
•  » » » 8 months ago, # ^ |   +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...")
•  » » » » 8 months ago, # ^ |   +4 I like "find the maximize size" even more:)
•  » » » » 8 months ago, # ^ |   -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.
•  » » » » » 8 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » 8 months ago, # ^ |   +5 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
•  » » » » » » » 8 months ago, # ^ |   0 You can take 1 minute to fix your comment Like thisNowadays it feels like GrammarForces, 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. GLHFBtw 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.
•  » » » » » 8 months ago, # ^ |   +9 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.
•  » » » » » 8 months ago, # ^ |   +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.
•  » » 8 months ago, # ^ |   0 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".
•  » » » 8 months ago, # ^ |   0 Yeah, I definitely meant at least as hard. And unfortunately I know nothing about "bit-parallelism".
•  » » » » 8 months ago, # ^ |   0 https://cses.fi/problemset/task/1685Could you help me in this? I find out it similar to the above problem.
•  » » » » » 8 months ago, # ^ |   0 Just count the sources and sinks in SCC and then output the maximum of them.
•  » » » » 8 months ago, # ^ |   -6 Bitsets?
•  » » » » » 8 months ago, # ^ |   0 Oh, I've never heard of that name. Still I can only think of improving the naive solution, which wouldn't be even close.