거짓말 - 백준 1043

골드4

유니온 파인드 문제라는 것 같은데

나는 그래프 탐색처럼 풀었다.

나중에 유니온 파인드 복습해야겠다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	// n,m
	int n, m;
	cin >> n >> m;
	int q;
	cin >> q;
	vector<int> known;
	vector<bool> bKnown(n,false);
	vector<bool> bDay(m, false);
	for (int i = 0; i < q; i++) {
		int c;
		cin >> c;
		known.push_back(c-1);
	}
	vector<vector<bool>> bPartys = vector<vector<bool>>(m, vector<bool>(n, false));
	for (int i = 0; i < m; i++) {
		int k = 0;
		cin >> k;
		for (int u = 0; u < k; u++) {
			int p;
			cin >> p;
			bPartys[i][p-1] = true;
		}
	}


	while (!known.empty()) {
		int w = known.back();
		bKnown[w] = true;
		known.pop_back();

		vector<int> days;

		for (int i = 0; i < m; i++) {
			if (bPartys[i][w] == true) {
				if (bDay[i] == false) {
					days.push_back(i);
					bDay[i] = true;
				}
			}
		}

		for (int a : days) {
			for (int i = 0; i < n; i++) {
				if (bPartys[a][i] == true) {
					if (bKnown[i] == false) {
						known.push_back(i);
					}
				}
				bPartys[a][i] = true;
			}
		}

	}
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		for (int k = 0; k < n; k++) {
			if (bPartys[i][k] == false) {
				cnt++;
				break;
			}
		}
	}
	int cntd = 0;
	for (int i = 0; i < m; i++) {
		if (bDay[i] == false) {
			cntd++;
		}
		
	}
	cout << cntd;
	//cout << endl;
	//cout << cnt;

}