[백준] 1043 거짓말 [자바]

 

 

---

https://www.acmicpc.net/board/view/85017

글 읽기 - 3% 입구 컷 당하네요 ㅠㅠ (주석있음, 발상 설명있음, 예제 다 통과)

https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-1043-%EA%B1%B0%EC%A7%93%EB%A7%90-JAVA%EC%9E%90%EB%B0%94

[백준] 1043 : 거짓말 (JAVA/자바)

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static int[] parent;
	static int N;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 		N = Integer.parseInt(st.nextToken());
 		int M = Integer.parseInt(st.nextToken());
 		
 		parent = new int[N+1];
 		boolean[] trueman = new boolean[N+1];
 		st = new StringTokenizer(br.readLine(), " ");
 		int k = Integer.parseInt(st.nextToken());
 		
 		for(int i = 0; i < k; i++) {
 			int a = Integer.parseInt(st.nextToken());
 			trueman[a] = true;
 		}
 		
 		for(int i = 1; i <= N; i++) {
 			parent[i] = i;
 		}
 		
 		int[][] print = new int[M][];
 		
 		for(int i = 0; i < M; i++) {
 			st = new StringTokenizer(br.readLine(), " ");
 			int tmp = Integer.parseInt(st.nextToken());
 			print[i] = new int[tmp];
 			int min = 0;
 			for(int j = 0; j < tmp; j++) {
 				print[i][j] = Integer.parseInt(st.nextToken());
 				if(min == 0) {
 					min = print[i][j];
 				}
 				else {
 					union(min, print[i][j]);
 				}
 			}
 		}
 		
 		boolean[] visit = new boolean[N+1];
 		for(int i = 1; i <= N; i++) {
 			if(trueman[i] && !visit[i]) {
 				int root = find(i);
 				for(int j = 1; j <= N; j++) {
 					if(find(j) == root) {
 						trueman[j] = true;
 						visit[j] = true;
 					}
 				}
 			}
 		}
 		
 		int answer = M;
 		for(int i = 0; i < M; i++) {
 			boolean infection = false;
 			for(int j = 0; j < print[i].length; j++) {
 				if(trueman[print[i][j]]) {
 					infection = true;
 				}
 			}
 			if(infection)
 				answer--;
 		}
 		System.out.println(answer);
 	}
 	static int find(int x) {
 		if(x == parent[x]) {
 			return x;
 		}
 		return parent[x] = find(parent[x]);
 	}
 	static void union(int a, int b) {
 		a = find(a);
 		b = find(b);
 		if(a != b) {
 			parent[b] = a;
 		}
 	}
}