need help in a union-find problem

Revision en1, by hiddentesla, 2016-08-06 05:59:15

so yesterday i just learned the union-find data structure, and i found this problem:

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:

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

Tags union-find, kattis


  Rev. Lang. By When Δ Comment
en1 English hiddentesla 2016-08-06 05:59:15 1209 Initial revision (published)