Makise_Kurisu's blog

Complexity analysis of complement graph traversal
By Makise_Kurisu, 5 years ago, In English

Hi, I was trying to solve this standard problem on complement graph traversal. Following are 2 almost similar solutions where one TLE's and the other passes, I'm not able to see where is the inefficiency coming in for the TLE solution, is it the complexity or just poor implementation.
TLE SOLUTION
AC SOLUTION
I understand the complexity of the second solution is $$$\mathcal{O}((N+M)\log N)$$$ as the number of times we check if an edge is present or not is $$$\mathcal{O}(M)$$$, but I'd be grateful if someone can outline the issue/complexity with/of the TLE solution.

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

»
5 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

Consider a graph with $$$0$$$ edges. Obviously everything is connected in such a graph. In the TLE version, when you first enter the dfs function, nx contains all other nodes. Then, when you loop through everything in nx, you dfs to each of those individually. Now in the next call of dfs, everything is in the unvisited set, excluding the first node that was visited. Now nx contains every node other than the first node. Continuing with this logic, in the first call of dfs nx is of size $$$n$$$, then $$$n-1$$$, then $$$n-2$$$, until it's of size $$$1$$$. In total, this is $$$\mathcal{O}(n^2)$$$. The AC version fixes this by ensuring that you never add some node to nx if you've already done so, preserving the $$$\mathcal{O}((N+M)\log{}N))$$$ complexity you mentioned.

→ Reply