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を例に、どのような値がマッピングされるかイメージ図にした。

f:id:d_tutuz:20180725224900p:plain

       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");
        }

ポイント

値の代表値を取ることでまとめることができる。(代表値でまとめる)

類題

C - ロト2