백준 1043번 거짓말 C++

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

 

유니온 파인드를 이용했다.

 

지민이를 0이라고 하고 처음에 진실을 아는 사람들을 0과 같은 그룹으로 넣었다.

그리고 각 파티에 참여하는 사람들을 전부 같은 그룹에 넣었다.

그리고 다시 파티에 참여하는 사람들을 검사하면서 전부 0과 다른 그룹이면 거짓말을 할 수 있는 파티이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using ll = long long;

vector<int> parent;
vector<int> height;

int GetParent(int n) {

	if (n == parent[n]) 
		return n;

	parent[n] = GetParent(parent[n]);
	return parent[n];
}

void Merge(int u, int v) {

	u = GetParent(u);
	v = GetParent(v);

	if (u == v)
		return;

	if (height[u] > height[v])
		swap(u, v);

	parent[u] = v;

	if (height[u] == height[v])
		height[v]++;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	parent.resize(n + 1);
	height.resize(n + 1);
	vector<vector<int>> party(m, vector<int>());
	for (int i = 0; i <= n; i++) {
		parent[i] = i;
		height[i] = 1;
	}
	int cnt;
	cin >> cnt;
	for (int i = 0; i < cnt; i++) {
		int num;
		cin >> num;
		Merge(0, num);
	}
	for (int i = 0; i < m; i++) {
		cin >> cnt;
		int lastNum;
		cin >> lastNum;
		party[i].push_back(lastNum);
		for (int j = 1; j < cnt; j++) {
			int num;
			cin >> num;
			Merge(lastNum, num);
			lastNum = num;
			party[i].push_back(num);
		}
	}
	int ans = 0;
	for (int i = 0; i < m; i++) {
		bool canBluff = true;
		for (int j = 0; j < party[i].size(); j++) {
			if (GetParent(0) == GetParent(party[i][j]))
				canBluff = false;
		}
		if (canBluff)
			ans++;
	}
	cout << ans;
};