金色4-白駿1043嘘

12333 ワード
アルゴリズムの問題-解決 テキストリンク

うそ


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

方法


まず、真実を知っている人を含めたパーティーの人は、真実を知っている人になります.そのため、真実を知っているすべての人をチェックし、一人を含むパーティーがあれば排除し、残りのパーティーの数を印刷します.

に答える


真実を知っている人を既知のキューに追加します.そして既知の人を一人ずつ出して、パーティーごとにその人が含まれているかどうかをチェックします.含めて、パーティーに参加したすべての人を確認して既知のキューに入れ、check配列で真実を確認した人は繰り返しキューに入れません.また、このパーティションをcheck party配列にチェックして削除します.既知のキュー内の次のメンバーを特定する場合は、削除されたパーティションを確認する必要がないため、スキップを続行します.

コード#コード#

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool checked[51];
bool checked_party[50];
vector<vector<int>> party;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	int k;
	cin >> k;

	queue<int> known;

	for (int i = 0; i < k; i++)
	{
		int temp;
		cin >> temp;
		known.push(temp);
	}

	for (int i = 0; i < M; i++)
	{
		vector<int> t;
		party.push_back(t);

		int p;
		cin >> p;
		for (int j = 0; j < p; j++)
		{
			int temp;
			cin >> temp;
			party[i].push_back(temp);
		}
	}

	while (!known.empty())
	{
		int person = known.front();
		known.pop();

		for (int i = 0; i < M; i++)
		{
			if (checked_party[i])
				continue;

			for (int j = 0; j < party[i].size(); j++)
			{
				if (party[i][j] == person)
				{
					checked_party[i] = true;

					for (int l = 0; l < party[i].size(); l++)
					{
						if (checked[party[i][l]])
							continue;
						known.push(party[i][l]);
					}
					break;
				}
			}
		}
	}

	int answer = 0;

	for (int i = 0; i < M; i++)
	{
		if (!checked_party[i])
			answer++;
	}

	cout << answer << '\n';

	return 0;
}
Ratpack入門 (3) - hello world 詳解
オレンジ練習1-データ処理