[Java] BOJ1043, 백준 - 거짓말

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

1043번: 거짓말

 

유니온파인드 응용 문제이다.
boolean[] know 배열을 이용하여 진실을 아는 그룹을 체크해주면 된다.
유니온파인드 기초만 탄탄하다면 응용하기 어렵지 않은 문제

<문제풀이>

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

public class Main {

	private static int[] parent;
	private static boolean[] know;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = parse(st.nextToken()); // 사람 수
		int m = parse(st.nextToken()); // 파티 수
		st = new StringTokenizer(br.readLine());
		int p = parse(st.nextToken()); // 진실을 아는 사람 수
		know = new boolean[n + 1]; // 진실을 알고있는 사람의 정보
		for (int i = 0; i < p; i++)
			know[parse(st.nextToken())] = true;
		int[] party = new int[m]; // 파티의 루트

		makeSet(n);

		for (int i = 0; i < m; i++) { // 파티 개수
			st = new StringTokenizer(br.readLine());

			p = parse(st.nextToken()); // 파티에 오는 사람 수
			int a = parse(st.nextToken()); // 첫 번째 사람
			party[i] = a;
			for (int j = 0; j < p - 1; j++) // 같은 파티 사람들은 모두 한 그룹에 넣자
				union(a, parse(st.nextToken()));
		}

		int cnt = 0;
		for (int i = 0; i < m; i++) {
			if (!know[find(party[i])])
				cnt++;
		}
		System.out.println(cnt);
	}

	private static void makeSet(int n) {
		parent = new int[n + 1];
		for (int i = 1; i <= n; i++)
			parent[i] = i;
	}

	private static int find(int a) {
		if (a == parent[a])
			return a;
		else
			return parent[a] = find(parent[a]);
	}

	private static void union(int a, int b) {
		int ra = find(a);
		int rb = find(b);
		if (ra != rb) {
			if (know[ra] || know[rb]) {
				// 둘 중 한 그룹이라도 진실을 알고있다면
				know[rb] = true;
				know[ra] = true;
			}
			parent[rb] = ra;
		}
	}

	private static int parse(String s) {
		return Integer.parseInt(s);
	}
}