うそ

2083 ワード
Union Find 白駿 分離セット テキストリンク
白駿1043
この問題は志敏が大げさな話をするチームの数を求める問題だ.この時、ジミンの物語の真実を知っている人に、パーティーごとに番号をあげます.
この問題を解決するために、真相を知っている人が所属するチームを除いて、チームの数が答えになりました.
あるパーティーで真実を聞く人もいれば、別のパーティーで大げさな話を聞くときも大げさなことを言ってはいけないからだ.
=>複数のパーティーに参加した人が真実を知っていれば、彼の所属するすべてのパーティーを排除しなければならないという意味です.そのため、一人が複数のパーティーに属している場合は、それらのパーティーを1つの集合にする必要があります.
union-findを使用してコレクションを作成します.
真実を知っている人を単独でベクトルに入れる.
行列をベクトル配列に組み込む.
そしてパーティーごとに真実を知っている人がいるかどうかを確認します.
=>find関数は、真実を知っている人の両親とパーティーごとに属する人の両親が同じかどうかを決定するために使用できます.
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> truth;
vector<int> party[51];
int parent[51];
int find(int x) {
	if (parent[x] == x) return x;
	else return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x == y) return;
	else {
		if (x > y) parent[x] = y;
		else parent[y] = x;
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) parent[i] = i;

	int t;
	cin >> t;
	while (t--) {
		int x;
		cin >> x;
		truth.push_back(x);
	}

	int cnt = 0;
	for (int i = 0; i < m; i++) {
		int x;
		int flag = 0;
		cin >> x;

		if (x >= 1) {
			for (int j = 0; j < x; j++) {
				int y;
				cin >> y;
				party[i].push_back(y);

				if (j != 0) merge(party[i][0], y);

			}
		}
	}

	for (int j = 0; j < m; j++) {
		int flag = 0;
		for (int k = 0; k < party[j].size(); k++) {
			for (int i = 0; i < truth.size(); i++) {
				if (find(truth[i]) == find(party[j][k])) {
					cnt++;
					flag = 1;
					break;
				}
			}
			if (flag) break;
		}
	}
	cout << m - cnt << '\n';
}
[翻译]Goが嫌いなのは君が取るに足らない人だからだ.
【PHP7.4】レガシーな仕様はどんどんしまっちゃおうねぇ