LunaticPriest's blog

By LunaticPriest, history, 5 weeks ago, In English,

Hello, I'm solving a basic connected components . My code is this . I tried switching to bitsets and a map instead of vectors, and also wrote my dfs iteratively in case of stack overflow. What can be the problem? Thanks!

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

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

You are using O(n^2) amounts of memory, which is too much.

When you try to access an element in a map in c++, if the element isn't there the default value of that element is inserted into the map, so your dfs blows up the memory.

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

    what do you suggest? Should I use a set and access in logn time, or are there any better ways to achieve this?

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

    When I used a set, I got TLE this time.

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

      Your approach is wrong, i recommend reading the editorial

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

        Nope, my approach was correct, the only problem was that I was accessing all the map elements, which resulted in the creation of such nodes. This time, I used a bitmap as a visited array and didn't access all the elements. It passed all the tests.