DisJointSetUnion

help
, , ,
1

You are given n vertices and m groups containing vertices that are connected to each other.
find number of vertices related to each vertices .

INPUT

First line will have
N -Number of vertices.
Second line will have
M - Number of sub-groups
Next
2M lines will describe the M sub-groups in following way:

First line
K (the number of vertices in this sub-group)
Second line will contain K space seperated integers denoting vertex number (1−N) which belongs to this subgroup.

OUTPUT

Print N integers where i th integer will be the number of vertex that is connected to it.

CONSTRAIN
N<10^6
0<=M<=N
1<=K<=N

Sample testcase
7
4
3
2 5 4
2
1 2
1
1
2
6 7

Output:
4 4 1 4 4 2 2

2

For each group, join the given vertex using union/join() function and then for every integer 1 to n, print(size[root(i)])

3

Could you elaborate you logic

5

For each group just join all the vertices that have been given in that group using the very common,dsu’s, join() function. Now For printing the answer, run a loop from 1 to n & print size[root(i)] where root(i) function returns the root for the given node. and size[] array stores the respective size of the disjoint set.

For more clearity, refer:-DSU