sbereghici's blog

HELP please ... Problems with STL::Multiset
By sbereghici, history, 9 years ago, In English

I'm trying to solve a problem using Union Find, for storing Connected Components of a graph, and a Multiset for ordering the Components' Weights ... but i'm getting "SIGSECV ( Abort Called ) "... here is my code Link

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

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Line 18 should be Father[f1] = Father[f2];.

The reason you get a runtime error is as follows: Let's say f1 is different from a. Since you only change the parent pointer of a, the parent pointer of f1 still points to f1. However, the weight of f1 is removed from the multiset. So if you call the merge function again with f1, the program will try to erase Weight[f1] from the multiset. If the weight is no longer present though, Order.find(Weight[f1]) returns Order.end(), and calling erase on that produces a runtime error.

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

this was from ongoing contest : https://www.hackerrank.com/contests/morgan-stanley-2015/leaderboard ..

→ Reply