[백준] C++ 거짓말(1043)

만약 누군가 진실을 알고 있다면 거짓말을 하면 안 된다.

 

근데 이 문제에서 조금 헷갈렸던 점은 파티를 여는 순서가 있는지 아니면 동시에 파티를 여는지가 좀 헷갈렸다.

문제를 해결해 보니 동시에 파티를 여는 문제였는데 만약 동시에 파티를 열게 되면 사람이 몸을 쪼개서 가야 하나?? 1/2등분에서 파티에 참석? 약간 이런 부분 때문에 문제를 이해하기 쉽지 않았다.

 

문제를 해결하는 방법은

각 파티에 참여하는 사람들이 주어지는데 각 파티의 첫 번째 사람을 파티장으로 임명해서 문제를 해결한다.

 

위 예제로 보면

첫 번째 파티에서 파티장은 1번이고 1번과 2번을 Union한다.

두 번째 파티에서 파티장은 3번이고 3번과 3번을 Union한다

세 번째 파티에서 파티장은 2번이고 2번과 3번을 Union하고 2번과 4번을 Union한다.

 

이렇게 파티장을 임명하고 Union을 하게 되면 관련이 있는 파티들은 묶이게 된다.

 

파티장과 진실을 알고 있는 사람이 같은 집합에 속해있으면 그 파티는 과장된 이야기를 할 수 없는 파티이다.

(파티마다 파티장과 진실을 알고 있는 사람들(여러 명)을 비교해야 함.)

 

#include <iostream>
#include <vector>
using namespace std;
int Find(int num);
void Union(int a, int b);
int arr[100];
vector<int> v;
vector<int>party[100];
int main(void)
{
	int N, M = 0;
	int count = 0;
	cin >> N >> M >> count;
	for (int i = 0; i < count; i++)
	{
		int num = 0;
		cin >> num;
		v.push_back(num);
	}

	for (int i = 1; i <= N; i++)
	{
		arr[i] = i;
	}

	for (int i = 1; i <= M; i++)
	{
		int num = 0;
		cin >> num;
		int first = 0;
		for (int j = 0; j < num; j++)
		{
			int temp = 0;
			cin >> temp;
			party[i].push_back(temp);
			if (j == 0)
			{
				first = temp;
			}
			Union(first, temp);
		}
	}

	int result = 0;

	for (int i = 1; i <= M; i++)
	{
		int sig = 0;
		int super = party[i][0];
		for (int j = 0; j < v.size(); j++)
		{
			if (Find(super) == Find(v[j]))
			{
				sig = 1;
				break;
			}
		}
		if (sig == 0)
		{
			result++;
		}
	}
	cout << result;

	return 0;
}

int Find(int num)
{
	if (arr[num] == num)
	{
		return num;
	}
	else
	{
		arr[num] = Find(arr[num]);
	}
	return arr[num];
}
void Union(int a, int b)
{
	int num1 = Find(a);
	int num2 = Find(b);

	arr[num2] = num1;
}