거짓말

https://www.acmicpc.net/problem/1043

소스코드

Main

    static int N,M;
    static int [] parents;
    static List<Integer> list;
    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());

        parents = new int[N+1];
        for (int i = 1; i < N+1; i++) {
            parents[i] =i;
        }
        st = new StringTokenizer(br.readLine());
        int en = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();

        if(en == 0){
            System.out.println(M);
            return;
        }else{
            for (int i = 0; i < en; i++) {
                list.add(Integer.parseInt(st.nextToken()));
                //진실을 아는 사람 노드를 list에 넣는다.
            }
        }

        List<Integer>[] party = new ArrayList[M];
        for (int i = 0; i < M; i++) {
            party[i] = new ArrayList<>();
            //파티 그룹 갯수 만큼 리스트 크기 생성.
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int pn = Integer.parseInt(st.nextToken());

            int x = Integer.parseInt(st.nextToken());
            party[i].add(x);
            //x가 속한 리스트를 루트노드로 설정해
            for (int j = 1; j < pn ; j++) {
                int y = Integer.parseInt(st.nextToken());
                union(x,y);
                //진실을 아는 사람들만 묶어서 party 집합을 만든다.
                party[i].add(y);
            }
        }

        int cnt=0;
        for (int i = 0; i < M; i++) {
            boolean check = true;
            for (int num: party[i]) {
                if(list.contains(find(parents[num]))){
               //루트노드가 진실을 아는 사람이라면  break;
                check =false;
                break;
            }
            }
            if(check){
                cnt++;
            }

            }

        System.out.println(cnt);

        }

union

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

find

 public static void union(int x, int y){
       int rx= find(x);
       int ry= find(y);

       if(list.contains(ry)){
           int tmp =rx;
           rx = ry;
           ry = tmp;
       }

       parents[ry] =rx;
    }

생각 할 것

UNION, FIND 알고리즘 관련 이해
부모 배열을 어떻게 써야될지 감이 아직 안잡힌듯 하다.

참고

https://loosie.tistory.com/463#h1