C++の練習を兼ねて, AtCoder Beginner Contest 157 の 問題D (D – Friend Suggestions) を解いてみた.
■感想.
1. 解説見る前に, AC版となったので, 良かったと思う, 一番時間を使った点は, ブロック関係を考慮して, 減算するためのロジックに気付くところだったと思う.
2. 幅優先探索の復習が出来たので, 良かった思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 157解説をご覧下さい.
■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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <bits/stdc++.h> using namespace std; using vvi = vector<vector<int>>; using P = pair<int, 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 a first #define b second #define pb push_back const int MAX = 101010; int connection[MAX]; // 連結成分番号を保存. int appearance[MAX]; // 連結成分番号の出現回数. int ans[MAX]; vvi F(MAX); // 友達関係. vector<P> B; // ブロック関係. // グラフを幅優先探索する. // https://ja.wikipedia.org/wiki/幅優先探索 // ※bfsの動作確認用. // @param G: グラフ. // @param s: グラフの探索開始頂点. // @param l: 連結成分番号(※1以上). // @return: 特に無し. void bfs(vvi &G, int s, int l){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. connection[s] = l; // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int u = q.front(); q.pop(); // 5. 取り出した要素を処理. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(connection[e] > 0) continue; if(connection[e] == 0 && e != s) connection[e] = l, q.push(e); } } return; } int main(){ // 1. 入力情報. int N, M, K; scanf("%d %d %d", &N, &M, &K); int a, b; rep(i, M){ scanf("%d %d", &a, &b); a--, b--; F[a].pb(b); F[b].pb(a); } rep(i, K){ scanf("%d %d", &a, &b); a--, b--; B.pb({a, b}); } // 2. 各頂点に対する連結成分番号を設定. int id = 0; rep(i, N) if(connection[i] == 0) bfs(F, i, ++id); // rep(i, N) printf("i=%d con=%d\n", i, connection[i]); // 3. 各連結成分番号の出現回数を計算. rep(i, N) appearance[connection[i]]++; // 4. 友達候補の集計. rep(i, N){ // 友達候補の数を計算. ans[i] += appearance[connection[i]]; // 自分自身は, 減算. ans[i]--; // 友達関係を減算. ans[i] -= F[i].size(); } // 5. ブロック関係を減算. rep(i, K){ a = B[i].a; b = B[i].b; // 同じ連結成分にある場合だけ, 減算. if(connection[a] == connection[b]) ans[a]--, ans[b]--; } // 6. 出力. rep(i, N){ printf("%d", ans[i]); if(i < N - 1) printf(" "); } 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 134 135 136 137 138 139 140 141 142 143 |
[入力例] 4 4 1 2 1 1 3 3 2 3 4 4 1 [出力例] 0 1 0 1 ※AtCoderテストケースより [入力例] 5 10 0 1 2 1 3 1 4 1 5 3 2 2 4 2 5 4 3 5 3 4 5 [出力例] 0 0 0 0 0 ※AtCoderテストケースより [入力例] 10 9 3 10 1 6 7 8 2 2 5 8 4 7 3 10 9 6 4 5 8 2 6 7 5 3 1 [出力例] 1 3 5 4 3 3 3 3 1 0 ※AtCoderテストケースより [入力例] 5 4 1 1 2 1 3 1 4 1 5 2 3 [出力例] 0 2 2 3 3 [入力例] 20 25 4 18 10 10 1 6 7 11 2 17 11 8 2 13 1 19 18 18 17 2 5 6 19 12 15 8 4 11 10 7 3 12 11 10 9 6 4 16 17 20 5 19 13 2 13 4 17 5 15 8 15 4 20 7 2 12 19 5 11 [出力例] 16 13 17 14 14 15 15 15 17 14 13 15 15 0 15 17 14 15 14 16 [入力例] 21 11 5 1 2 3 2 4 3 6 5 8 9 7 6 11 10 10 9 21 20 20 19 18 17 12 3 15 3 16 4 14 5 13 6 [出力例] 2 1 1 2 1 0 1 2 1 1 2 0 0 0 0 0 0 0 1 0 1 [入力例] 19 16 6 12 1 12 2 5 1 3 2 5 4 4 3 7 4 15 13 13 10 17 11 18 11 11 8 8 6 6 7 16 14 14 9 19 17 19 18 10 7 7 9 9 3 10 5 [出力例] 9 9 9 8 9 9 9 9 1 1 8 9 0 0 1 1 10 10 0 |
■参照サイト
AtCoder Beginner Contest 157