[java 백준] 1043번 거짓말

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
 
    public static int n;
    public static int m;
 
    public static int secretN;
    public static ArrayList<Integer>secret=new ArrayList<>();
    public static int parents[];
 
 
 
    public static int sum=0;
 
    public static int find(int a){
        if(parents[a]==a){
            return a;
        }
       return find(parents[a]);
    }
 
    public static void union(int a,int b){
        a=find(a);
        b=find(b);
        if(secret.contains(b)){
            int tmp=a;
            a=b;
            b=tmp;
        }
        parents[b]=a;
    }
 
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
 
       Scanner sc=new Scanner(System.in);
       n=sc.nextInt();
       m=sc.nextInt();
       parents=new int[n+1];
       for(int i=1;i<=n;i++){
           parents[i]=i;
 
       }
       secretN=sc.nextInt();
       if(secretN!=0){
 
           for(int i=0;i<secretN;i++){
               secret.add(sc.nextInt());
           }
       }
       List<Integer>[]list=new ArrayList[m];
       for(int i=0;i<m;i++){
           list[i]=new ArrayList<>();
       }
       for(int i=0;i<m;i++){
           int num=sc.nextInt();
           int x=sc.nextInt();
           list[i].add(x);
           for(int j=1;j<num;j++){
               int y=sc.nextInt();
               union(x,y);
               list[i].add(y);
 
           }
       }
 
       for(int i=0;i<m;i++){
           boolean flag=true;
           for(int num:list[i]){
               //연쇄해서 부모를 찾아냄
               if(secret.contains(find(parents[num]))){
                   flag=false;
                   break;
               }
           }
           if(flag){
               sum++;
           }
       }
 
       System.out.println(sum);
 
 
 
 
 
 
 
 
 
 
    }
 
}

유니온 파인드로 풀 수 있는 문제였다. 

 

문제를 풀면서 중요한 부분이

union 함수였는데 b가 a보다 커서 parents[b]=a가 되는게 아니였다. 

b가 진실을 아는 그룹에 속해있으면 a와 b를 swap해서 parents[b]=a가 되게끔 한다. 그러면 진실을 아는 b가 a로 swap되면서 부모가 될 수 있다. (진실을 아는 사람이 부모여야함!!)