けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 061 B - Counting Roads (5Q, 灰色, 200 点)

AtCoder AtCoder200点 ABC-B 灰色diff NoviSteps5Q グラフ グラフの頂点の次数に着目する 【問題集】グラフの入門 そのまま覚えたい易しい教育的典型問題 各kに対して

「グラフ」の基礎問題！　グラフを知らなくても解ける。

問題概要

N 個の都市 ( 1, 2, \dots, N) があり、 M 本の道路がある。 i 番目の道路は、都市 a_{i} と都市 b_{i} を結んでいる。同じ 2 つの都市を結ぶ道路は、1 本とは限らない。

各都市から他の都市に向けて、何本の道路が伸びているか求めよ。

制約

  • 1 \le N, M \le 50
  • a_{i} \neq b_{i}

考えたこと

この手の問題でよくあることとして、都市の番号を 0-indexed で考えることにしよう。つまり、都市の番号を 1, 2, \dots, N と考えるのではなく、 0, 1, \dots, N-1 と考えることにしよう。また、その際には、 i 番目の道路が結ぶ 2 つの都市 a_{i}, b_{i} をデクリメント（1 を引くこと）するのを忘れないようにしよう。

さて、このとき、次のデータを管理しよう。

  • num[v]：都市 v から他の都市へと向けて、伸びている道路の本数

最初は num 全体を 0 で初期化しておく。そして、各道路 (a_{i}, b_{i})（デクリメント済のもの）に対して、その両端の都市に対する num の値をインクリメントすればよい。具体的には、次のようにすればよい。

num[a[i]]++;
num[b[i]]++;

すべての道路に対して、この処理を終えたあと、都市 0, 1, \dots, N-1 についての num の値を出力すればよい。

コード

#include <bits/stdc++.h>
using namespace std;
                                 
int main() {
    int N, M;
    cin >> N >> M;

    vector<int> num(N, 0);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;  // デクリメントする

        num[a]++;
        num[b]++;
    }

    // 出力
    for (int i = 0; i < N; i++) cout << num[i] << endl;
}