문제 설명

문제 분석

슈도코드

구현

public class 거짓말쟁이가되긴싫어_1043 {
    static int[] parent;
    static int result = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(); // 사람의 수
        int M = scan.nextInt(); // 파티의 수
        int knowNum = scan.nextInt();// 진실을 아는 사람 수
        int[] knowArr = new int[knowNum]; // 진실을 아는 사람들의 번호 배열
        
        // 진실을 아는 사람들
        for (int i = 0; i < knowNum; i++) {
            knowArr[i] = scan.nextInt();
        }
        
        // 사람들 번호 넘버링
        int[] people = new int[N+1]; 
        for (int i = 1; i <= N; i++) {
            people[i] = i;
        }

        ArrayList<Integer>[] party = new ArrayList[M];
        // 파티 데이터 저장
        for (int i = 0; i < M; i++) {
            party[i] = new ArrayList<>();
            int partySize = scan.nextInt();
            for (int j = 0; j < partySize; j++) {
                party[i].add(scan.nextInt());
            }
        }

        parent = new int[N + 1];
        // 대표 노드 자기 자신으로 초기화
        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }

        // 각 파티에 참여한 사람들을 그룹화
        for (int i = 0; i < M; i++) {
            int firstPeople = party[i].get(0);
            for (int j = 1; j < party[i].size(); j++) {
                union(firstPeople, party[i].get(j));
            }
        }

        // 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장할 수 없음
        for (int i = 0; i < M; i++) {
            boolean isPossible = true;
            int current = party[i].get(0);
            for (int j = 0; j < knowArr.length; j++) {
                if(find(current) == find(knowArr[j])) {
                    isPossible = false;
                    break;
                }
            }

            if (isPossible) {
                result++;
            }
        }
        System.out.println(result);
    }

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

    private static int find(int node) {
        if(node == parent[node]) {
            return node;
        } else {
            return parent[node] = find(parent[node]);
        }
    }

}