[백준][C++] 1043: 거짓말

문제 링크: https://www.acmicpc.net/problem/1043

 

입력 조건이 n, m<=50이기 때문에 여러 방법으로 풀 수 있는데요 제일 간단한 방법인 union-find로 풀어봤습니다.

문제 핵심은 진실을 아는 사람과 같은 파티에 있으면 진실을 아는 것과 동일하게 된다는 것입니다. 파티에 진실을 아는 사람이 있으면 그 파티 참가자 전부 진실을 알게 되는 셈이고, 그 파티 참가자가 다른 파티에 가면 다른 파티 또한 전부 진실을 알게 됩니다.

 

그럼 union-find로 진실을 아는 사람들의 집합을 늘려가면 되는데요, 계산 편의를 위해 진실을 아는 0번 사람을 가상으로 추가해줍니다. 그러면 어떤 사람이 진실을 아는 집합에 있는지 아닌지 확인하려면 0번 사람의 parent를 확인해보면 됩니다.

각 파티마다 참가자들은 일심동체이기 때문에 파티 참가자들끼리 merge를 해줍니다. 이렇게 하면 나중엔 자연스럽게 진실을 아는 집합과, 모르는 집합(들)로 집합이 분리가 되겠죠? 확인할 때는 0번 사람의 parent랑 비교하면 됩니다.

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


int n, m;
int parent[51];

void init() {
	for (int i = 0; i < n; ++i)
		parent[i] = i;
}

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;

	parent[u] = v;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m;
	++n;
	init();

	vector<bool> truth(n);
	truth[0] = true;

	int t;
	cin >> t;
	while (t--) {
		int tmp;
		cin >> tmp;
		truth[tmp] = true;
	}

	for (int i = 1; i < n; ++i)
		if (truth[i])
			merge(0, i);

	vector<vector<int>> parties(m);
	for (auto& party : parties) {
		int p;
		cin >> p;

		party.resize(p);
		for (auto& i : party)
			cin >> i;

		for (int i = 1; i < p; ++i)
			merge(party[0], party[i]);
	}

	int counter = 0;
	for (auto& party : parties) {
		if (find(party[0]) != find(0))
			++counter;
	}
	cout << counter << '\n';
		
	return 0;
}

유니온파인드를 한 2주만에 짰더니 find 구현할 때 실수를 했었습니다. find 함수에서 return parent[u] = find(u)로 썼더니 오랜만에 스택오버플로 오류를 봤습니다;