The Big News

Shivangi is 19 and doesn't know how to cook. She is standing next to a large group of aunties(of age around 50 years). Unfortunatly one of those aunties knows this "big news" and is planning to spread this news.

The spreading goes this way: $N$ Aunties are standing in $M$ sub-groups(one aunty can belong to more than one group) and if an aunty knows the news then she will spread it in all the groups she belongs to and then all the aunties of those groups will spread this news further.

If any aunty comes to know about this news the she will ask Shivangi "You are 19 and still don't know how to cook?"(aunty will not ask again). And She wants to answer them each by saying "You are 50 and you still dont know how to mind your own *uc*ing buisness?". She wants to know how many times does she needs to say this comeback.

Shivangi doesnt know which aunty knows about the news so you have to find for each of the N aunties that if she is the only one in the starting to know the news then in total how many aunties will know the news(how many times does Shivangi needs to use the comeback).

Example:

Input: 7
4
3
2 5 4
2
1 2
1
1
2
6 7
Output: 4 4 1 4 4 2 2 

Approach

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class TheBigNews {
    static int[] parent;
    static int[] size;
    public static void main(String args[] ) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N =Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        parent = new int[N+1];
        size = new int[N+1];
        for(int i=1;i<=N;i++){
            size[i]=1;
        }
        for(int m=0;m<M;m++){
            int K = Integer.parseInt(br.readLine());
            String[] s = br.readLine().split(" ");
            int p = Integer.parseInt(s[0]);
            for(int i=1;i<K;i++){
                int child = Integer.parseInt(s[i]);
                unite(p, child);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=N;i++){
            sb.append(size[getParent(i)]).append(" ");
        }
 
        System.out.println(sb);
 
    }
 
    public static int getParent(int node){
        if(parent[node]==0)return node;
        return parent[node] = getParent(parent[node]);
    }
 
    public static void unite(int node1, int node2){
        node1 = getParent(node1);
        node2 = getParent(node2);
        if(node1!=node2){
            if(size[node1]<size[node2]){
                int tmp = node2;
                node2=node1;
                node1=tmp;
            }
            parent[node2]=node1;
            size[node1]+=size[node2];
        }
    }
    
}