r3novatio's blog

By r3novatio, history, 5 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +39
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

deleted.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    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)

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

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

»
5 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

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

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

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What is the problem source?

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

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

Share it please.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

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

        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.

»
5 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

    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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

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

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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

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

              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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          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.

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

    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".

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

      Yeah, I definitely meant at least as hard. And unfortunately I know nothing about "bit-parallelism".