The Big News Hackerearth

#1

Getting wrong answer
Question link:-https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/the-big-news-64c8dcee/description/
My code link https://ide.codingblocks.com/s/330986

#2

@Bhawna
Will get back to you shortly.

#3

@Bhawna
This is the loop for the time when we take inputs for the groups.
while(m–){
int k;
cin >> k;
int root;
cin >> root;
int child;
for(int i = 1;i < k;i++){
cin >> child;
G.unite(child, root);
}
}

When I ran your code, it was not getting accepted. But I just modified the loop a bit and it worked out. I am still unable to figure out. Use the above piece of code and I will try to get back to you ASAP. Here what I have done is that I have merged all the members of the subgroup to one element only.

Will get back to you asap.

#4

Even writing your code ,I didn’t get AC…

#5

plz look at my union by rank ,I have not used size array

#6

@Bhawna
Union by rank does use a size array. You give preference to a sub group which has a bigger size.

#7

Then why my code is not getting accepted if I am merging all the members of the subgroup to one element only
link: https://ide.codingblocks.com/s/331258
Also tell me what was wrong in first code if we are merging one by one??

#8

@Bhawna
Try using the size array concept. You are increasing the size of one but are not decreasing that of the other to zero.

#9

I have reduced other’s rank to zero but still getting WA
and I think it is not necessary to reduce rank of other as zero as for rank we will always compare rank of superparent not own rank

#10

@Bhawna
Found the mistake. Your code also got accepted.
cout<<G.r[G.p[pk]]<<" ";

Here you have directly used G.p[pk]. Its not at all certain that the parent of pk at this point is the actual parent of the subgroup.
You should rather call G.f(pk). Using this, you will be able to access the actual parent of the subgroup.

If my answer is able to resolve your query, please mark the doubt as resolved.

#11

Got your point thanks…

#12

@Bhawna
If my answer is able to resolve your query, please mark the doubt as resolved.