AtCoderログ：0067 - ABC 061 B

問題

問題文

$N$ 個の都市があり、$M$ 本の道路があります。$i~(1 \le i \le M)$
番目の道路は、都市 $a_i$ と都市 $b_i$ $(1 \le a_i,b_i \le N)$ を双方向に結んでいます。同じ $2$ つの都市を結ぶ道路は、$1$ 本とは限りません。
各都市から他の都市に向けて、何本の道路が伸びているか求めてください。

制約

・$2 \le N, M \le 50$
・$1 \le a_i,b_i \le N$
・$a_i \ne b_i$
・入力は全て整数である。

収録されている問題セット

• AtCoder に登録したら次にやること (第07問類題)

回答

回答1 (AC)

各都市に通っている道路の本数を保存する配列 path を用意し、初期値を 0 に設定します。都市 a から 都市 b の道路がある場合、path.at(a) と path.at(b) に 1 を加える操作を全ての道路に対して処理すれば良いでしょう。コードは以下のようになりました。

abc061b-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  int a, b;
  vector<int> path(n+1,0);
  for ( int i=0; i<m; i++ ) {
    cin >> a >> b;
    path.at(a) += 1;
    path.at(b) += 1;
  }

  for ( int i=1; i<=n; i++ ) {
    cout << path.at(i) << endl;
  }
}

調べたこと

AtCoder の解説 → コンテスト全体の解説

後半は回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0066 - ABC 213 A
• 次の記事 → AtCoderログ：0068 - ABC 213 B