백준 1043 : 거짓말

2차원 배열을 만들 때 List로 만들면 각각 new로 초기화가 필요한 것 인지

유니온 파인드 사용

wrapper class - 기본 자료형을 객체로 다루기 위해 쓰이는 클래스. 값을 외부에서 변경할 수 없음

 

왜 쓰는지

1. 자바의 컬렉션 클래스들은 객체만 저장 가능 - 기본형에서 wrapper class로 boxing 필요

2. 자바의 제네릭 타입을 사용할 때 필요

3. null 값 저장 가능

4. 유틸리티 메서드 제공

import java.io.*;
import java.util.*;


public class Main {
    //Integer와 int 차이
    public static int N,M;//1<=N,M<=50
    public static int[] parent;
    public static int find(int n){
        if(parent[n]==n) return n;
        return parent[n] = find(parent[n]);
    }
    public static void merge(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa!=pb){
            if(pa < pb)
                parent[pb] = pa;
            else parent[pa] = pb;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(bf.readLine());
        int truth = Integer.parseInt(st.nextToken());
        parent = new int[N+1];
        for(int i = 0; i <= N; i++) parent[i] = i;
        List<Integer>[] party = new ArrayList[M];//기억
        for(int i=0; i < M; i++) {//초기화 필수
            party[i] = new ArrayList<>();
        }
        for(int i = 0; i < truth; i++){
            int p = Integer.parseInt(st.nextToken());
            merge(0,p);
        }
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(bf.readLine());
            int K = Integer.parseInt(st.nextToken());

            for(int j = 0; j < K; j++){
                party[i].add(Integer.parseInt(st.nextToken()));
            }
            for(int j = 1; j < K; j++){
                merge(party[i].get(j-1), party[i].get(j));
            }
        }

        int res = 0;
        for(int i = 0; i < M; i++){
            boolean has_truth = false;
            for(int j = 0; j < party[i].size(); j++){
                if(find(party[i].get(j))==0){
                    has_truth = true;
                    break;
                }
            }
            if(!has_truth) res++;
        }
        System.out.print(res);





    }
}