ある配列のvalueを別の配列の添字にして問題を解く (ABC061 B - Counting Roads)

初心者は紙に書いて考えないと手こずる系の問題。

atcoder.jp

問題概略

N個の都市とM本の道路がある。
i番目の都市は、他の都市と1本の道路で結ばれている。
このときi番目の都市が、他のいくつの都市と結ばれているか?
出力は、i行目にi番目の結果を出力せよ。

入力

N M
a_1 b_1
...
a_M b_M

方針

次の2通りの方針が考えられる。

• 2重ループを用いて、全探索を行う。計算量はO(NM)。
• 「i番目の都市が他の都市といくつ道路をつないでいるかを管理する配列」を用意して数え上げる。計算量はO(N + M)。

今回は2つ目の方法を用いて解く。

配列を用意する

今回用意する配列は、以下の情報を格納する。
「i番目の都市が他の都市といくつ道路をつないでいるかを管理する配列」・・・(A)
この(A)は以下のように考える。

aおよびbの0番目から「都市aから伸びている道路の数」と「都市bから伸びている道路の数」をカウントしていく。
たとえば0番目の入力が「1 5」であれば、配列(A)の1番目の都市と5番目の都市をそれぞれインクリメントする。
このカウント結果を上記の配列に格納する。
最後に、この配列を0番目から順に標準出力して完了。

実装する

2重配列でもよいが、今回は連想配列を用いた。

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main(){
    int N, M; cin >> N >> M;
    vector<int> a(M), b(M); rep(i, M) cin >> a[i] >> b[i];

    map<int, int> res; rep(i, N) res[i] = 0;
    rep(i, M) {
        res[a[i] - 1]++;
        res[b[i] - 1]++;
    }

    rep(i, N) {
        cout << res[i] << endl;
    }
}