I am assuming that you have already understood the problem statement otherwise go back and read the problem statement once again: PROBLEM STATEMENT
If you are not familiar with DSU and path compression, I suggest you to go and this post first.
There are 'N' survivors and 'Q' queries in each test case.
In each query two survivors become friends uniting their respective groups into a larger group. And after each query you have to tell the difference between the group size of largest group and smallest group, for this purpose we will use STL, we can use SET, MULTISET, or MAP, which will keep the group size of each group.
As set, multiset and map keeps the data sorted, for difference between smallest and biggest group you can subtract the first element from last element.
We are keeping a 'parent' array which keeps parent of each survivor, i.e., parent[A] store the parent of Ath survivor. Intially every body is their own parent :P
For all the group members we will find root using root function. Suppose A,B,C,D and E are in a group and parent[A]=A, parent[B]=A, parent[C]=B, parent[D]=C and parent[E]=D.
Then root(A) = root(B) = root(C) = root(D) = root(E).
After every query we will do union operation if and only if their roots are not equal. After every union we will add group1_size + group2_size into the multiset and will remove group2_size from multiset.
I hope you can implement the code for this problem yourself otherwise refer to the following code:
If you are not familiar with DSU and path compression, I suggest you to go and this post first.
There are 'N' survivors and 'Q' queries in each test case.
In each query two survivors become friends uniting their respective groups into a larger group. And after each query you have to tell the difference between the group size of largest group and smallest group, for this purpose we will use STL, we can use SET, MULTISET, or MAP, which will keep the group size of each group.
As set, multiset and map keeps the data sorted, for difference between smallest and biggest group you can subtract the first element from last element.
We are keeping a 'parent' array which keeps parent of each survivor, i.e., parent[A] store the parent of Ath survivor. Intially every body is their own parent :P
For all the group members we will find root using root function. Suppose A,B,C,D and E are in a group and parent[A]=A, parent[B]=A, parent[C]=B, parent[D]=C and parent[E]=D.
Then root(A) = root(B) = root(C) = root(D) = root(E).
After every query we will do union operation if and only if their roots are not equal. After every union we will add group1_size + group2_size into the multiset and will remove group2_size from multiset.
I hope you can implement the code for this problem yourself otherwise refer to the following code:
thanks. u helped me to solve this question.
ReplyDeletebut u should optimize your code. u can do union by rank also.
ReplyDeleteYes. That would be necessary optimization.
Delete