VerbalKint's blog

By VerbalKint, history, 6 months ago, In English,

I was solving this problem: https://www.spoj.com/problems/BREAK/ I figured that for a DAG, we can solve it by using indegree vector and simple dfs. Going though some online editorials, I noticed that there was mention of Strongly Connected Components. Can anyone tell me the intuition behind using SCC in this question. Any help is appreciated. Thanks

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, in SCC we can reach any node to another. So, if the graph is SCC then answer is obviously $$$N$$$ for each number. Moreover, you can make a DAG with considering this SCC's as a vertex. You know how to solve it for DAG, so you only need to apply there and make correct calculations.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. I got the idea behind using SCC in this question,

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The idea behind SCCs is, that you can create a DAG from any arbitrary graph by contracting each SCC into a single node. The resulting graph is called "condensation graph", and is guaranteed to be a DAG. This is also fine, since the number of nodes every node in a SCC can reach is equal.

Why does having a DAG helps? Quite a bunch of problems can be solved efficiently on DAGs using DP. E.g. most of the game theory problems are based on that. However you can't apply DP on that problem. A first idea would be the recursion $$$f(v) = 1 + \sum_{(v, u) \in E} f(u)$$$, where $$$f(v)$$$ counts the number of reachable vertices from $$$v$$$. However it doesn't work because you double count vertices. E.g. look at the following graph and compute $$$f(1)$$$:

1->2
|  |
v  v
3->4

So even if you have a DAG, you need to do the trivial approach by running a DFS from each nodes, resulting in a runtime of $$$O(n m)$$$. And you can do that also on the normal graph in the same time complexity.

So does SCC help at all? Yes, because the test cases are not very good. I just tried to submit a solution without SCC, and it TLEd. And a solution with SCC got AC. On a random graph the condensation graph is usually a lot smaller than the original graph, which gives a decent performance boost (you only need to do one DFS for each SCC, instead one for each node, have less nodes and edges in general, ...). However it is possible to create graphs with $$$\Theta(n^2)$$$ edges, which correspond to their condensation graphs. In such a case you have a big graph, and computing the SCCs and the condensation graph will do nothing at all.

Note: it is possible to compute the answer faster than $$$O(n m)$$$. One method is to compute the transitive closure of the graph using matrix exponentiation. You can see in $$$A^n$$$ which vertex is reachable from which one, where $$$A$$$ is the adjacency matrix. Using binary exponantiation you can copmute $$$A^n$$$ in $$$O(n^3 \log n)$$$ time. If you use a faster matrix multiplication algorithm you can reduce the $$$n^3$$$ factor, and this pdf describes a way of getting rid of the logarithmic factor by first computing the condensation graph. However I doubt that such an approach can get the problem accepted.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot for the explanation. I also got TLE without SCC. I learned something new from this question. I'll try to solve more SCC problems now. Thanks again :)