1043번: 거짓말

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

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, M, KnowTruth, KnowTruthIndex, Answer;
int KnowPeopleArray[51];
int UnionArray[51];
int PartyIndex{};
vector<int> Graph[51];
vector<int> Partys[51];

void DFS(int PersonIndex)
{
	if (Graph[PersonIndex].empty())
	{
		UnionArray[PersonIndex] = PartyIndex;
		return;
	}

	for (size_t i = 0; i < Graph[PersonIndex].size(); ++i)
	{
		if (UnionArray[Graph[PersonIndex][i]]) continue;
		UnionArray[Graph[PersonIndex][i]] = PartyIndex;
		DFS(Graph[PersonIndex][i]);
	}
}

void MakeGroup()
{
	int CntPartyPeople{};
	int PushIndex{ 0 };
	for (int i = 0; i < M; ++i)
	{
		cin >> CntPartyPeople;
		vector<int> VecPartyPeople;
		for (int j = 0; j < CntPartyPeople; ++j)
		{
			int PeopleIndex{};
			cin >> PeopleIndex;
			VecPartyPeople.push_back(PeopleIndex);
		}

		Partys[PushIndex] = VecPartyPeople;
		++PushIndex;

		// Make graph
		for (int j = 1; j <= CntPartyPeople - 1; ++j)
		{
			Graph[VecPartyPeople[j]].push_back(VecPartyPeople[j - 1]);
			Graph[VecPartyPeople[j - 1]].push_back(VecPartyPeople[j]);
		}
	}
}

void MakeGroupArray()
{
	for (int i = 1; i <= N; ++i)
	{
		if (0 >= UnionArray[i])
		{
			++PartyIndex;
			DFS(i);
		}
	}
}

void Solve()
{
	vector<int> TruthPartyIndex;
	for (int i = 1; i <= N; ++i)
	{
		if (KnowPeopleArray[i] == 1)
		{
			TruthPartyIndex.push_back(UnionArray[i]);
		}
	}

	for (int i = 0; i < M; ++i)
	{
		bool bIsTruth = true;
		for (int j = 0; j < Partys[i].size(); ++j)
		{
			int GroupIndex = UnionArray[Partys[i][j]];
			for (int k = 0; k < TruthPartyIndex.size(); ++k)
			{
				if (GroupIndex == TruthPartyIndex[k])
				{
					bIsTruth = false;
					break;
				}
			}
			if (false == bIsTruth)
			{
				break;
			}
		}
		if (bIsTruth)
		{
			++Answer;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	//freopen("input.txt", "rt", stdin);

	cin >> N >> M >> KnowTruth;

	if (0 < KnowTruth)
	{
		for (int i = 0; i < KnowTruth; ++i)
		{
			cin >> KnowTruthIndex;
			KnowPeopleArray[KnowTruthIndex] = 1;
		}
	}
	else
	{
		cout << M;
		return 0;
	}

	MakeGroup();

	MakeGroupArray();

	Solve();

	cout << Answer;

	return 0;
}