득이공간

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

PS/알고리즘 문제풀이

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

쟁득 2024. 3. 4. 18:57
 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

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