[백준] 1043번 거짓말 (gold 4

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args )throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());

        //아직 어떻게 사람들 관계가 어떻게 연결되는지 모르므로 입력을 그냥 받아놓음.
        ArrayList<Integer>[] arr=new ArrayList[m];
        for(int i=0; i<m; i++){
            arr[i]=new ArrayList<>();
        }

        //사람간의 관계 true이면 연결됨
        boolean[][] map=new boolean[n+1][n+1];

        //사실을 아는사람
        boolean[] real=new boolean[n+1];
        st=new StringTokenizer(br.readLine());
        int t=Integer.valueOf(st.nextToken());
        for(int i=0; i<t; i++){
            real[Integer.valueOf(st.nextToken())]=true;
        }

        //파티 시작. 사람들 도착
        //파티케이스에 추가해서 누가왔는지
        //그리고 파티 처음온사람을 나머지와 그래프로 연결.
        //왜냐하면 후에 진실을 아는 사람에서 넓이우선을 나아가면 이와 연결된 사람들도 모두
        //체크가능하므로 결국 진실알게되는 사람들 판별가능
        for(int i=0; i<m; i++){
            st=new StringTokenizer(br.readLine());
            int pn=Integer.valueOf(st.nextToken());
            int fp=Integer.valueOf(st.nextToken());
            arr[i].add(fp);
            for(int j=0; j<pn-1; j++){
                int temp=Integer.valueOf(st.nextToken());
                map[fp][temp]=true;
                map[temp][fp]=true;
                arr[i].add(temp);
            }
        }

        Queue<Integer> que=new LinkedList<>();
        boolean[] visit=new boolean[n+1];
        for(int i=1; i<=n; i++){
            if(real[i]){
                que.offer(i);
                visit[i]=true;
            }
        }

        //진실아는 사람과 연결관계 파악
        while(!que.isEmpty()){
            int temp=que.poll();

            for(int i=1; i<=n; i++){
                if(map[temp][i]){
                    real[i]=true;
                    if(!visit[i]) {
                        visit[i] = true;
                        que.offer(i);
                    }
                }

            }
        }
		//파티마다 진실아는 사람 체크해서 있으면 패스
        //없으면 +1;
        int answer=0;
        for(int i=0; i<m; i++){
            boolean find=false;
            for(int j=0; j<arr[i].size(); j++){
                if(real[arr[i].get(j)]){
                    find=true;
                    break;
                }
            }
            if(!find){
                answer++;
            }
        }

        bw.write(answer+"");
        bw.flush();

    }
}