C++の練習を兼ねて, 第１０回 アルゴリズム実技検定 過去問 の 問題H (連結成分) を解いてみた.
■感想.
1. 問題Hは, 方針を絞り込めたので, AC版に到達できたと思う
2. Union-Find木 の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 初めは, 深さ優先探索の方針で, 提出したものの TLE版(test_10.txt ～ test_12.txt)となったので, Union-Find木 を利用して, 随時, 頂点情報を, マージする方針に変更した背景がある.
但し, マージの際に, 根に相当する頂点で, 場合分けしないと, TLE版(test_07.txt)となったので, 注意が必要と感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト 第１０回 アルゴリズム実技検定 過去問 の 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題H／TLE版).
|
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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define all(x) x.begin(), x.end() set<int> G[202020]; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [&](auto&& self, int cur, int bef, set<int> &st) -> void { // 訪問済みチェック. if(st.count(cur)) return; // 訪問済設定. st.insert(cur); // 隣接頂点. for(auto &nex : G[cur]) if(nex != bef) self(self, nex, cur, st); }; // 3. クエリ回答. rep(i, Q){ // 3-1. クエリ入力情報. int t; scanf("%d", &t); // 3-2. クエリ 1. if(t == 1){ int u, v; scanf("%d %d", &u, &v); --u; --v; G[u].insert(v); G[v].insert(u); } // 3-3. クエリ 2. if(t == 2){ int u; scanf("%d", &u); --u; // 訪問経路保存. set<int> st; dfs(dfs, u, -1, st); // 出力. vi ans; for(auto &x : st) ans.pb(x); int n = ans.size(); rep(i, n) printf("%d%s", ans[i] + 1, (i < n - 1) ? " " : "\n"); } } return 0; } |
■C++版プログラム(問題H／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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back set<int> st[202020]; // https://github.com/atcoder/live_library/blob/master/uf.cpp // UnionFind // coding: https://youtu.be/TdR816rqc3s?t=726 // comment: https://youtu.be/TdR816rqc3s?t=6822 // -> 一部改変. struct UnionFind{ vi d; UnionFind(int n = 0): d(n, -1) {} int find(int x){ return (d[x] < 0) ? x : (d[x] = find(d[x])); } bool unite(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(d[x] > d[y]) swap(x, y); d[x] += d[y]; d[y] = x; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return -d[find(x)]; } }; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); // 2. 初期化. UnionFind uf(N + 2); rep(i, N){ uf.unite(i, i); st[i].insert(i); } // 3. クエリ回答. rep(i, Q){ // 3-1. クエリ入力情報. int t; scanf("%d", &t); // 3-2. クエリ 1. if(t == 1){ int u, v; scanf("%d %d", &u, &v); --u; --v; // 連結の場合は, 次へ. if(uf.same(u, v)) continue; // 連結でなかった場合は, マージ. st[u].insert(v); st[v].insert(u); int ou = uf.find(u); int ov = uf.find(v); uf.unite(u, v); int o = uf.find(u); // マージ. // o = ou. if(o == ou){ for(auto &x : st[ov]) st[o].insert(x); st[ov].clear(); continue; } // o != ou (o = ov を 想定). for(auto &x : st[ou]) st[o].insert(x); st[ou].clear(); } // 3-3. クエリ 2. if(t == 2){ int u; scanf("%d", &u); --u; int o = uf.find(u); // 出力. vi ans; for(auto &x : st[o]) ans.pb(x); int n = ans.size(); rep(i, n) printf("%d%s", ans[i] + 1, (i < n - 1) ? " " : "\n"); } } 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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
[入力例] 5 7 1 1 2 2 2 1 3 4 2 5 1 1 4 2 1 2 4 [出力例] 1 2 5 1 2 3 4 1 2 3 4 ※AtCoderテストケースより [入力例] 1 2 2 1 2 1 [出力例] 1 1 ※AtCoderテストケースより [入力例] 3 3 1 1 2 2 1 1 1 2 [出力例] 1 2 ※AtCoderテストケースより [入力例] 3 7 1 1 2 2 1 1 1 2 1 1 3 2 1 1 2 3 2 2 [出力例] 1 2 1 2 3 1 2 3 [入力例] 7 10 1 1 7 2 7 1 1 4 1 5 6 1 2 3 2 1 1 2 5 2 3 1 1 3 2 1 [出力例] 1 7 1 4 7 2 3 5 6 1 2 3 4 5 6 7 [入力例] 10 18 2 1 1 1 2 1 3 4 2 2 1 5 6 1 1 2 1 7 8 2 5 1 9 10 1 1 3 1 7 8 2 3 1 7 9 2 8 1 2 5 2 4 1 6 8 2 10 [出力例] 1 1 2 5 6 1 2 3 4 7 8 9 10 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 |
■参照サイト
第１０回 アルゴリズム実技検定 過去問
Union-Find木