ABC097 D問題（Equals）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）097 D問題をC++で解いてみました。ABC097は、2018年5月12日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Equals（Difficulty : 1270）

問題の詳細は、リンク先をご覧ください。

ABC097 D問題 Equals

UnionFind で数列の要素を仲間分けします。AtCoder Problems による Difficulty は 1270 でした。

解答案

C++ プログラム例（ABC097D）

与えられた $(x_i, y_i)$ を同じグループだと考えます。同じグループの数同士は交換ができます。同じグループか判定するには、UnionFind が使えます。

プログラムの補足です。

• UnionFind は、ACL（AtCoder Library）の実装を使いました（2、４行目）。
• 読み込んだ xi と yi を merge します（22行目）。
• Pi と i が同じグループであれば、変数 result の値を増やします（27ー29行目）。
• 最後に result を出力します（32行目）。

以下が、C++プログラムです。

#include <bits/stdc++.h>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> p(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> p[i];
	}
	vector<int> x(m), y(m);
	for (int i = 0; i < m; ++i) {
		cin >> x[i] >> y[i];
	}

	dsu uf(n + 1);
	for (int i = 0; i < m; ++i) {
		uf.merge(x[i], y[i]);
	}

	int result = 0;
	for (int i = 1; i <= n; ++i) {
		if (uf.same(p[i], i)) {
			++result;
		}
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

UnionFind の応用例です。繰り返し応用問題を解き、理解度を上げたいです。

引き続き ABC の問題を紹介していきます。