need help in a union-find problem

Правка en1, от hiddentesla, 2016-08-06 05:59:15

so yesterday i just learned the union-find data structure, and i found this problem: https://open.kattis.com/problems/almostunionfind

my approach is as following: implement basic union-find, but also add array sum[] for the sum of the group and freq[], the number for elements in the group

i also "made" the group using a vector of vector, so if there is a group {1,3,5} and 1 is the leader, the representing vector is

{1,3,5} or {1,5,3} (leader is always in the front, other element is random depending on the union, the function of this is for the "2" function, where how i handle it is i first find the "leader" of the group (lets call it indeks i), then the element must be in v[i], so i erase the element from the vector, make the next first element in the vector the leader and adjust the rest of the vector, if the leader of the new vector (lets call it indeks j) is not i, swap it the vector i with vector j clear vector i;

my code: https://ideone.com/vZVvCn

however, im getting WA :( and i tried to debug it but no luck, can someone point out a counter case?

also, if there is a more optimal approach then my approach, please give me hints

Теги union-find, kattis

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский hiddentesla 2016-08-06 05:59:15 1209 Initial revision (published)