C++の練習を兼ねて, AtCoder Beginner Contest 049 の 問題D (D – 連結 / Connectivity) を解いてみた.
■感想.
1. 解説上, Union-Find木について触れられていたので, Union-Find木 に 慣れるため, 解き直しした.
本家のサイトABC049/ARC065解説をご覧下さい.
■C++版プログラム(問題D／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
// 解き直し. // ABC049/ARC065解説. // https://img.atcoder.jp/arc065/editorial.pdf // 以下のライブラリを使ってみる. // 素集合データ構造(Union-Find) // https://ei1333.github.io/luzhiled/snippets/structure/union-find.html #include <bits/stdc++.h> using namespace std; int ar[200001]; int br[200001]; struct UnionFind{ vector<int> data; UnionFind(int sz){ data.assign(sz, -1); } // 頂点 x, y の 結合. bool unite(int x, int y){ x = find(x), y = find(y); if(x == y) return false; if(data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } // 頂点 k を 探索. int find(int k){ if(data[k] < 0) return k; return data[k] = find(data[k]); } // 頂点 k を含む集合 の 大きさ. int size(int k){ return (-data[find(k)]); } }; int main(){ // 1. 入力情報取得. int N, K, L; int p, q; scanf("%d %d %d", &N, &K, &L); UnionFind ufc(N); // 道路で連結. UnionFind uft(N); // 鉄道で連結. // 2. 道路で連結している都市. for(int i = 0; i < K; i++){ scanf("%d %d", &p, &q); p--, q--; ufc.unite(p, q); } // 3. 鉄道で連結している都市. for(int i = 0; i < L; i++){ scanf("%d %d", &p, &q); p--, q--; uft.unite(p, q); } // 4. 各都市に, Union-Findでの根の都市番号を保存(道路, 鉄道). for(int i = 0; i < N; i++){ ar[i] = ufc.find(i); br[i] = uft.find(i); } // 5. (ar[i], br[i]) の 出現回数を集計. map<pair<int, int>, int> m; for(int i = 0; i < N; i++){ pair<int, int> p = make_pair(ar[i], br[i]); m[p]++; } // 6. 各都市について, 5. で確認した出現回数を出力. for(int i = 0; i < N; i++){ pair<int, int> p = make_pair(ar[i], br[i]); printf("%d ", m[p]); } // 7. 後処理. return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
[入力例] 4 3 1 1 2 2 3 3 4 2 3 [出力例] 1 2 2 1 ※AtCoderテストケースより [入力例] 7 4 4 1 2 2 3 2 5 6 7 3 5 4 5 3 4 6 7 [出力例] 1 1 2 1 2 2 2 ※AtCoderテストケースより [入力例] 10 6 4 1 2 1 4 1 7 1 10 1 5 1 3 4 5 1 5 4 7 7 10 [出力例] 5 1 1 5 5 1 5 1 1 5 [入力例] 12 9 3 10 11 11 12 12 9 9 8 4 7 5 6 6 3 2 3 2 1 7 1 6 9 8 10 [出力例] 1 1 1 1 1 1 1 2 1 2 1 1 |