ABC049-D:連結 / Connectivity(400)
問題
https://beta.atcoder.jp/contests/abc049/tasks/arc065_b
考え方
各頂点が連結なのかどうかを判定する必要があるため、素集合データ構造を使用することが思いつく。道路の K 個のクエリによって N を素集合データ構造 set1 に分割する。同様に鉄道の L 個のクエリで N 頂点を素集合データ構造 set2 に分割する。ここで頂点 i と 頂点 j が set1 も set2 も連結である時は以下のように表すことができる。
i と j が連結 ⇔ set1[i] = set1[j] かつ set2[i] = set2[j]
各頂点 i に対してそれぞれ [0, n-1] の頂点 j と比較して個数を計算すると O(N2) となって間に合わない。set1 について i と j が同じグループに属するとはすなわち、set1上で i の代表値と j の代表値が同じということである。set2 についても同様である。よって各頂点 i について set1 と set2 の代表値をペアで保持し、同一のペアの個数を数えることで set1 も set2 も同一のグループに属する頂点数を高速に求めることができる。
参考までにサンプル3を例に、どのような値がマッピングされるかイメージ図にした。
public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(), k = in.nextInt(), l = in.nextInt(); DisjointSet set1 = new DisjointSet(n); for (int i = 0; i < k; i++) { int p = in.nextInt()-1; int q = in.nextInt()-1; set1.unite(p, q); } DisjointSet set2 = new DisjointSet(n); for (int i = 0; i < l; i++) { int r = in.nextInt()-1; int s = in.nextInt()-1; set2.unite(r, s); } Map<Pair<Integer, Integer>, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { map.merge(new Pair<Integer, Integer>(set1.findSet(i), set2.findSet(i)), 1, Integer::sum); } for (int i = 0; i < n; i++) { int ans = map.get(new Pair<Integer, Integer>(set1.findSet(i), set2.findSet(i))); if (i > 0) { out.print(" "+ans); } else { out.print(ans); } } out.print("\n"); }
ポイント
値の代表値を取ることでまとめることができる。(代表値でまとめる)