[백준] 1043 : 거짓말

문제

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

 

 

 

입출력

 

4 3
0
2 1 2
1 3
3 2 3 4

3

---

아이디어

파티 참여한 사람들을 그룹지어 하나의 그룹으로 취급하고

진실을 알고있는 사람들도 하나의 그룹으로 취급한 뒤 

파티 참석 가능 여부를 확인하기 위해 

파티 i에 참석한 사람의 그룹장 == 진실을 알고 있는 사람의 그룹장 확인 

 

 

 

코드 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N, M; // 사람의 수, 파티의 수 https://www.acmicpc.net/problem/1043
	static List<Integer> truths;
	static int[] parents;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		truths = new ArrayList<>(); // 이야기를 아는 사람의 수
		st = new StringTokenizer(br.readLine());
		int cnt = Integer.parseInt(st.nextToken());
		for (int i = 0; i < cnt; i++) {
			int truthId = Integer.parseInt(st.nextToken());
			truths.add(truthId);
		}
		parents = new int[N + 1];
		for (int i = 1; i < N + 1; i++) {
			parents[i] = i;
		}
		for (int i = 0; i < truths.size() - 1; i++) { // 진실을 알고있는 사람들을 하나의 그룹으로 만든다 
			int a = truths.get(i);
			int b = truths.get(i + 1);
			union(a, b);
		}
		int truthSetRootId = -1;
		if (truths.size() != 0) {
			truthSetRootId = find(truths.get(0));
		}

		List<Integer>[] party = new ArrayList[M];
		for (int i = 0; i < M; i++) {
			party[i] = new ArrayList<>();
		}

		// i번째 파티에 x가 참석
		for (int i = 0; i < M; i++) { // 파티 개수만큼 반복
			st = new StringTokenizer(br.readLine());
			int pplCnt = Integer.parseInt(st.nextToken());

			List<Integer> partyPpl = new ArrayList<>();
			for (int j = 0; j < pplCnt; j++) {
				partyPpl.add(Integer.parseInt(st.nextToken()));
			}
			party[i] = partyPpl;

			for (int j = 0; j < party[i].size() - 1; j++) {
				union(party[i].get(j), party[i].get(j + 1)); // 파티i 참석자도 하나의 그룹으로 만든다 
			}
		}

		int partyCnt = 0;
		for (int i = 0; i < M; i++) {
			boolean isPossible = true; // 참여 가능 여부 
			int leader = party[i].get(0); // 파티i의 참석자
			for (int j = 0; j < truths.size(); j++) {
				if (find(truths.get(j)) == find(leader)) { // 진실을 말한 사람이 속해있는 그룹 == 파티 i의 참석자가 속해 있는 그룹
					isPossible = false; // 파티 참여 불가 
					break;
				}
			}
			if (isPossible) {
				partyCnt += 1;
			}
		}

		System.out.println(partyCnt);
	}

	static int find(int x) {
		if (x == parents[x]) {
			return x;
		}
		return parents[x] = find(parents[x]);
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if (x < y) {
			parents[x] = y;
		} else {
			parents[y] = x;
		}
	}

}