#백준_1043 거짓말 - Java 자바

# 유형 : 탐색, 그래프
# 어떻게 접근할지 생각해보다가 그래프를 그려보니 방법이 떠올랐다. 정점 사이의 연결을 확인해주면 된다.

진실을 알고있는 사람이 참여한 파티를 큐에 넣으면서 BFS를 통해 파티들을 체크하며 해결하는 방식으로 접근하면 된다. 

 

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1043 {
    static int N,M,K;
    static int cnt=0;
    static ArrayList<Integer> party[];
    static ArrayList<Integer> people[];
    static ArrayList<Integer> know;
    static boolean visit[];
    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());
        K = Integer.parseInt(st.nextToken());
        
        party = new ArrayList[M+1];
        for(int i=0; i<M+1; i++)
            party[i] = new ArrayList<>();
        
        people = new ArrayList[N+1];
        for(int i=0; i<N+1; i++)
            people[i] = new ArrayList<>();
        
        know = new ArrayList<>();
        visit = new boolean[M+1];
        
        for(int i=0; i<K; i++)
            know.add(Integer.parseInt(st.nextToken()));
        
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            for(int j=0; j<num; j++) {
                int val = Integer.parseInt(st.nextToken());
                party[i].add(val);
                people[val].add(i);
            }
        }
        
        
        bfs();
        
        System.out.println(cnt);
        
    }
    public static void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        
        // 진실을 알고있는 사람이 참여한 파티를 큐에 넣는다.
        for(int i=0; i<know.size(); i++) {
            for(int j=0; j<people[know.get(i)].size(); j++) {
                if(!visit[people[know.get(i)].get(j)]) {
                    visit[people[know.get(i)].get(j)] = true;
                    queue.add(people[know.get(i)].get(j));
                }
            }
        }
        
        while(!queue.isEmpty()) {
            int val = queue.poll();
            // 큐에는 진실을 알고있는 사람이 참여한 파티가 들어있으므로 하나씩 추출해나간다. 그 파티에 속한 사람들도 진실을 알아야하므로, 연결된 사람들을 체크한다.
            for(int i=0; i<party[val].size(); i++) {
                for(int j=0; j<people[party[val].get(i)].size(); j++) {
                    if(!visit[people[party[val].get(i)].get(j)]) {
                        visit[people[party[val].get(i)].get(j)] = true;
                        queue.add(people[party[val].get(i)].get(j));
                    }
                }
            }
        }
        
        for(int i=0; i<M; i++) 
            if(!visit[i])
                cnt++;
    }
}