問題概要

$N$ の人 $1, 2, \dots, N$ がいる。 $M$ 組の友達関係があって、 $i$ 組目の友達は人 $a_{i}$ と $b_{i}$ である。

人 1 の友達と、人 1 の友達の友達に相当する人 (人 1 を除く) が何人いるかを答えよ。

制約

$2 \le N \le 500$
$1 \le M \le 10000$

解法

この問題はグラフの練習問題といえる。グラフは vector<vector<int>> 型変数 (ここでは G とする) で管理するとよいことが多い。具体的には

G[v]：頂点 $v$ に隣接している頂点の番号を表す集合

というようにする。

さて、頂点 0 (0-indexed で考えるので、問題文でいう人 1 を頂点 0 とする) に隣接する頂点と、頂点 0 に隣接する頂点に隣接する頂点を求めたい。これらを重複なく列挙するために、バケットや集合を用意するとよいだろう。ここでは、サイズ $N$ のバケット

isin[v]： $v$ が答えであるとき True / そうでないとき False

を用意することにした。そうすると、頂点 0 に隣接する頂点と、頂点 0 に隣接する頂点に隣接する頂点を列挙する処理は、次のように実装できる。

vector<int> isin(N, false);
// 頂点 0 に隣接する頂点 v を走査していく
for (auto v : G[0]) {  
    isin[v] = true;  // 友達を入れる
    
    // 頂点 v に隣接する頂点 v2 を走査していく
    for (auto v2 : G[v]) {
        isin[v2] = true;  // 友達の友達を入れる
    }
}

ここで注意したいことは、頂点 $0$ に隣接する頂点 $v$ に隣接する頂点を走査していくとき、その中に頂点 $0$ も含まれることだ。これは最後に除外することに注意しよう。

次のコードで、計算量は $O(N + M)$ となる。

コード

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

int main() {
    int N, M, a, b;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; i++) {
        cin >> a >> b,  a--, b--;
        G[a].push_back(b), G[b].push_back(a);
    }

    // 友達と、友達の友達を入れていく
    vector<int> isin(N, false);
    for (auto v : G[0]) {
        isin[v] = true;  // 友達を入れる
        for (auto v2 : G[v]) {
            isin[v2] = true;  // 友達の友達を入れる
        }
    }
    int res = 0;
    for (int i = 1; i < N; i++) if (isin[i]) res++;
    cout << res << endl;
}