AtCoder が提供しているABC（AtCoder Beginner Contest）049 D問題をC++で解いてみました。ABC049は、2016年12月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 連結（Difficulty : 1996）
問題の詳細は、リンク先をご覧ください。
UnionFind を使う典型問題です。AtCoder Problems による Difficulty は 1996 でした。
解答案
C++ プログラム例（ABC049D）
道路で連結している都市を UnionFind 木 road に登録します（11ー16行目）。同じように、鉄道で連結している都市を UnionFind 木 rail に登録します（17ー22行目）。
各都市で道路で連結している根（road.leader()）と鉄道で連結している根（rail.leader()）の組み合わせをカウントして、その結果を出力します。
実装は、ACL（AtCorder Library）を使いました。以下が、C++プログラムです。
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main()
{
int n, k, L;
cin >> n >> k >> L;
dsu road(n + 1);
for (int i = 0; i < k; ++i) {
int p, q;
cin >> p >> q;
road.merge(p, q);
}
dsu rail(n + 1);
for (int i = 0; i < L; ++i) {
int r, s;
cin >> r >> s;
rail.merge(r, s);
}
map<pair<int, int>, int> m;
for (int i = 1; i <= n; ++i) {
++m[make_pair(road.leader(i), rail.leader(i))];
}
for (int i = 1; i <= n; ++i) {
cout << m[make_pair(road.leader(i), rail.leader(i))] << " \n"[i == n];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
過去の ABC には、適切な難易度の典型問題が多く出題されていると感じます。
引き続き ABC の問題を紹介していきます。
