arnav2004's blog

By arnav2004, history, 3 years ago, In English

I solving this problem Link to problem. I could not solve it hence checked other people's code. I saw this AC Code. AC Solution. I changed it just a little bit and it got runtime error. Runtime Error Code. As you can see the only difference is in the for loop in the 'dfs' function. Can anyone tell me the reason for the code to receive a runtime error.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Checking whether the set is empty or not also did not help.

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

You should never delete element in a range-based for loop. In the AC code, the element are deleted later after the for loop. If you still wanna delete element while iterating:

for(auto it = s.begin(); it != s.end(); ){
    if(/*delete condition here*/) it = s.erase(it); //return the next iterator
    else ++it;
}

I still prefer to delete outside the loop than delete inside the loop. From my experience, set is a magic data structure in C++, sometime you couldn't find where your code cause RTE without printing every possible variables, debugger can't help. So be careful, otherwise you will have a great time debugging hopelessly.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the info. Learnt something new.

    But still after iterating through iterators it's still giving runtime error. (This time on test 1). Here is the code that I wrote:

    for(auto x = unv.begin(); x != unv.end(); ) {
            if (bad.find(minmax(*x, v)) == bad.end()){
                int c = *x;
            	x = unv.erase(x);
            	dfs(c);
            }
            else x++;
        }
    
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Simply because unv is modified outside the loop. Assume currently we are in node u then Then we call dfs go to v and delete something in unv. When we go back to u, unv was modified.

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

      i have removed verdict RTE by first checking whether that element that you are iterating in loop is present or not, we are doing this because we have modified this set many times. 136610663