백준 1043 - 거짓말 (자바)

문제

풀이

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int[] parent;

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

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b) parent[b] = a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();// 사람 수
        int M = sc.nextInt(); //파티수

        parent = new int[N+1];
        for(int i=1; i<=N; i++) {
            parent[i] = i;
        }
        int t = sc.nextInt(); // 진실을 아는 사람 수
        int[] truth = new int[t];
        for(int i=0; i<t; i++) {
            truth[i] = sc.nextInt();
        }

        List<List<Integer>> parties = new ArrayList<>();
        for(int i=0; i<M; i++) {
            int k = sc.nextInt();
            List<Integer> p = new ArrayList<>();
            for(int j=0; j<k; j++) {
                p.add(sc.nextInt());
            }
            parties.add(p);

            for(int j=0; j<p.size()-1; j++) {
                union(p.get(j), p.get(j+1));
            }
        }
        sc.close();
        int answer = 0;
        for(List<Integer> p : parties) {
            boolean canLie = true;
            for(int person : p) {
                for(int tr : truth) {
                    if(find(person) == find(tr)) {
                        canLie = false;
                        break;
                    }
                }
                if(!canLie) {
                    break;
                }
            }
            if(canLie) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

거짓말을 하기 위해서는 해당 그룹에 진실을 아는 사람이 없어야 한다.
진실을 아는 사람을 루트로 집합을 만들고 그 그룹을 피하면 된다.
Union-Find를 이용해 풀이.