백준 1043 거짓말

백준 1043
이 문제는 지민이가 과장된 이야기를 할 수 있는 파티의 갯수를 구하는 문제이다. 이 때 지민이의 이야기의 진실을 알고 있는 사람이 주어지고 각 파티에 어떤 사람들이 오는지가 번호로 주어진다.

이 문제를 풀기 위해서는 결국 진실을 알고 있는 사람이 속한 파티들을 제외한 파티의 갯수가 답이 되게 된다.

어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 과장된 이야기를 할 수 없기 때문에
=> 결국 여러 파티에 겹처서 온 사람이 진실을 알고 있다면 그 사람이 속한 여러 파티들을 다 제외해줘야 한다는 뜻이다. 그러기 위해서 한 사람이 여러 파티에 속했다면 그 파티들을 모두 하나의 집합으로 만들 필요가 이다
이 때 union-find를 이용해서 집합을 만들었다.

진실을 아는 사람을 따로 하나의 벡터에 다 담아두고
파티들을 하나의 벡터 배열에 담아둔다.

그리고 각 파티마다 진실을 아는 사람이 있는지 확인을 해주면 된다
=> find 함수를 이용해서 진실을 아는 사람의 부모와 각 파티에 속한 사람들의 부모가 같은지 확인해주면 된다.

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> truth;
vector<int> party[51];
int parent[51];
int find(int x) {
	if (parent[x] == x) return x;
	else return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x == y) return;
	else {
		if (x > y) parent[x] = y;
		else parent[y] = x;
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) parent[i] = i;

	int t;
	cin >> t;
	while (t--) {
		int x;
		cin >> x;
		truth.push_back(x);
	}

	int cnt = 0;
	for (int i = 0; i < m; i++) {
		int x;
		int flag = 0;
		cin >> x;

		if (x >= 1) {
			for (int j = 0; j < x; j++) {
				int y;
				cin >> y;
				party[i].push_back(y);

				if (j != 0) merge(party[i][0], y);

			}
		}
	}

	for (int j = 0; j < m; j++) {
		int flag = 0;
		for (int k = 0; k < party[j].size(); k++) {
			for (int i = 0; i < truth.size(); i++) {
				if (find(truth[i]) == find(party[j][k])) {
					cnt++;
					flag = 1;
					break;
				}
			}
			if (flag) break;
		}
	}
	cout << m - cnt << '\n';
}