[Baekjoon] 1043번: 거짓말

🥅 문제

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

 

🔍 설계

파티에 최종적으로 진실을 알게 되는 사람이 한 명이라도 있으면, 거짓말을 할 수 없다.

 

파티에 진실을 아는 사람을 먼저 찾고, 있으면 파티에 있는 사람들을 진실을 아는 사람들의 집합으로 union 하려고 했는데, 이 방법은 파티 중 뒤에 진실을 아는 사람이 있으면, 앞에 파티에서는 진실을 아는 사람들의 집합으로 union할 수 없다.

 

단순하게 파티에 있는 사람들을 묶기만 하면, 진실을 아는 사람이 뒤쪽 파티에 나와도 뒤쪽 파티에서 진실을 아는 사람들의 집합으로 반영되기 때문에, 파티 각각에서 진실을 아는 사람이 없으면 총 파티 수에서 감소시키기만 하면 된다.

 

👊 풀이

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

int n, m, number, person, result = 0;
vector<int> parent(51);
vector<vector<int>> parties;

int find_parent(int x) {
	if (parent[x] != x) {
		return find_parent(parent[x]);
	}
	return x;
}

void union_parent(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a < b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;

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

	cin >> number;
	if (number == 0) {
		cout << m << "\n";
		return 0;
	}

	for (int i = 0; i < number; i++) {
		cin >> person;
		parent[person] = 0;
	}
	
	for (int i = 0; i < m; i++) {
		vector<int> party;
		cin >> number;
		for (int j = 0; j < number; j++) {
			cin >> person;
			party.push_back(person);
		}
		for (int j = 1; j < number; j++) {
			union_parent(party[0], party[j]);
		}
		parties.push_back(party);
	}

	int result = m;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < parties[i].size(); j++) {
			if (find_parent(parties[i][j]) == 0) {
				result -= 1;
				break;
			}
		}
	}
	cout << result << "\n";

	return 0;
}