[백준 C++] 1043 거짓말 - 분리집합

1043번: 거짓말

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

bool TFriend[51];
int Root[51];
int PartyPrimary[51];

int Find(int Node)
{
	if (Node == Root[Node])
	{
		return Node;
	}

	return Root[Node] = Find(Root[Node]);
}

void Union(int NodeA, int NodeB)
{
	int A = Find(NodeA);
	int B = Find(NodeB);
	
	int NewRoot = min(A, B);
	Root[A] = NewRoot;
	Root[B] = NewRoot;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N, M;
	cin >> N >> M;

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		int Friend;
		cin >> Friend;
		TFriend[Friend] = true;
	}

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

	for (int i = 1; i <= M; ++i)
	{
		int F;
		cin >> F;

		int Primary;
		cin >> Primary;
		PartyPrimary[i] = Primary;

		for (int j = 1; j < F; ++j)
		{
			int Cur;
			cin >> Cur;
			Union(Primary, Cur);
		}
	}

	int Cnt = M;
	for (int i = 1; i <= M; ++i)
	{
		int PartyRoot = Find(PartyPrimary[i]);

		bool bTParty = false;
		for (int j = 1; j <= N; ++j)
		{
			if (TFriend[j] && Find(j) == PartyRoot)
			{
				bTParty = true;
				break;
			}
		}

		if (bTParty)
		{
			--Cnt;
		}
	}

	cout << Cnt;
}

---

 

분리 집합 유형의 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 진실을 아는 친구 기록

2. 파티 정보 입력 - 각 파티에서 리더 친구를 지정하고 그 친구를 기준으로 해당 파티의 모든 친구들을 연결 (유니온-파인드 작업)

3. 모든 연결이 끝난 후, 각 파티를 순회 - 해당 파티의 리더 친구와 연결된 친구 중, 진실을 아는 친구가 있다면 카운드 다운