C++の練習を兼ねて, 競プロ典型 90 問 の 問題021 (Come Back in One Piece) を解いてみた.
■感想.
1. 実装方針を決めることができたこと, および, 過去問の実装を参照できたので, AC版に到達出来たと思う.
2. 強連結成分分解(Strongly Connected Component)について, 理解を深めることが出来たので, 非常に良かったと思う.
3. 問題021は, 過去問 AtCoder Beginner Contest 202 (E – Count Descendants) を一部拝借する形で, 実装に反映した.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題021 を ご覧下さい.
■C++版プログラム(問題021/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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using vvi = vector<vi>; using P = pair<int, int>; using PQ = priority_queue<P>; #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 a first #define b second #define pb push_back int memo[101010], t[101010], scc[101010]; LL gCount[101010]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vvi G1(N), G2(N); rep(i, M){ int a, b; scanf("%d %d", &a, &b); a--, b--; G1[a].pb(b); // 有向辺. G2[b].pb(a); // 有向辺(逆向き). } // 強連結成分分解(Strongly Connected Component). // https://manabitimes.jp/math/1250 // 2. 行き止まりの順番を保存. int idx = 0; PQ pq; auto dfs1 = [&](auto&& self, int c) -> void{ // 訪問済フラグ設定. memo[c] = 1; // 取り出した要素を処理. for(auto &n : G1[c]) if(!memo[n]) self(self, n); // 行き止まりの順番を保存. pq.push({++idx, c}); }; rep(i, N) if(!memo[i]) dfs1(dfs1, i); // 3. 強連結成分に分解. idx = 0; auto dfs2 = [&](auto&& self, int c) -> void{ // 連結成分番号設定. scc[c] = idx; // 取り出した要素を処理. for(auto &n : G2[c]) if(!scc[n]) self(self, n); }; while(!pq.empty()){ // 要素を取り出す. P p = pq.top(); pq.pop(); // 連結成分番号が設定済み. if(scc[p.b]) continue; // インクリメント. idx++; // 連結成分番号設定. dfs2(dfs2, p.b); } // 4. 各強連結成分の大きさを保存. rep(i, N) gCount[scc[i]]++; // 5. 集計. LL ans = 0; repx(i, 1, idx + 1) ans += gCount[i] * (gCount[i] - 1) / 2; // 6. 出力. printf("%lld\n", ans); 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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
[入力例] 4 7 1 2 2 1 2 3 4 3 4 1 1 4 2 3 [出力例] 3 ※AtCoderテストケースより [入力例] 100 1 1 2 [出力例] 0 ※AtCoderテストケースより [入力例] 9 11 1 2 2 1 2 9 2 3 3 6 6 7 7 8 8 6 3 4 4 5 3 5 [出力例] 4 [入力例] 12 18 1 2 2 1 5 1 2 3 4 2 3 8 3 4 4 6 4 6 4 7 4 5 8 11 11 12 12 8 8 9 9 10 10 8 10 8 [出力例] 20 [入力例] 17 21 1 2 2 3 4 1 4 3 8 4 3 8 10 8 10 11 11 12 8 12 9 12 7 9 9 13 5 7 6 5 7 6 14 13 16 14 16 15 15 13 17 13 [出力例] 13 [入力例] 23 38 1 3 3 1 3 2 2 4 3 16 16 17 17 18 18 17 3 18 4 6 6 4 1 5 5 1 5 6 5 19 20 5 19 20 19 21 21 22 22 23 23 22 23 19 6 7 6 7 7 9 8 7 8 9 9 10 10 11 11 9 11 15 15 11 10 12 12 10 12 13 13 14 14 13 14 15 [出力例] 51 |