[백준] 1043 거짓말 - 유니온파인드

문제 링크 : https://www.acmicpc.net/problem/1043

🍊해결방법

• 파티가 주어질 때마다 맨 처음 수를 기준으로 union하자
• 다시 파티들을 보면서 비밀을 아는 사람의 부모와 주어진 파티 참가자들의 부모가 같은지 판단

😀풀이

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

public class Main {

    static int N;
    static int M;
    static int[] arr;
    static List<Integer>[] list;
    static int[] parent;


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());

        arr = new int[t]; // 비밀을 아는 사람

        for(int i=0; i<t; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        parent = new int[N+1];

        for(int i=1; i<=N; i++){
            parent[i] = i;
        }

        list = new List[M];

        for(int i=0; i<M; i++){

            st = new StringTokenizer(br.readLine());

            int cnt = Integer.parseInt(st.nextToken());

            list[i] = new ArrayList<>();

            if (cnt == 0) continue;

            int p = Integer.parseInt(st.nextToken());

            list[i].add(p);

            for(int j=0; j<cnt-1; j++){
                int num = Integer.parseInt(st.nextToken());
                union(p, num);
                list[i].add(num);
            }
        }

        int ans = 0;


        for(int i=0; i<M; i++){
            boolean check = true;
            o : for(int x : list[i]){

                // 비밀을 알고있는 사람이 있는지
                for(int j=0; j<arr.length; j++){
                    // 비밀을 암
                    if(find(parent[x]) == find(arr[j])){
                        check = false;
                        break o;
                    }

                }

            }
            if (check) ans++;

        }


        System.out.println(ans);



    }// end main

    static void union(int a, int b){

        a = find(a);
        b = find(b);

        if (a == b)
            return;

        parent[b] = a;

    }

    static int find(int x){

        if (parent[x] == x){
            return x;
        }

        parent[x] = find(parent[x]);

        return parent[x];
    }

}