問題概要

頂点数 $N$ 、辺数 $M$ の単純な無向グラフが与えられます。 $i$ 番目の辺は、頂点 $A_{i}$ と頂点 $B_{i}$ を結んでいます。

各頂点 $v = 1, 2, \dots, N$ に対して、頂点 $v$ に隣接する頂点を小さい順に出力してください。

制約

$2 \le N \le 10^{5}$
$1 \le M \le 10^{5}$

解法

グラフをプログラム上でどのように扱った良いかを学べる問題ですね。詳しいことは、次の記事に書いたので、参考にしてもらえたらと思います。

algo-method.com

やるべきこととしては、次の図のように、各頂点に対して、それに隣接する頂点のリストを求めていきます。

これらの情報は、二次元配列 vector<vector<int>> 型の変数 G を用いて管理できます。頂点 $v$ に隣接する頂点の集合は G[v] と現せます。たとえば上図のグラフの場合、次のようになります。

G[0] = {5}
G[1] = {3, 6}
G[2] = {5, 7}
G[3] = {0, 7}
G[4] = {1, 2, 6}
G[5] = {}
G[6] = {7}
G[7] = {0}

具体的な実装方法については、解答例を参考にしてもらえたらと思います。

注意点：ダメな方法

グラフをプログラムで扱う方法として

is_connected[u][v] ← 頂点 $u, v$ を結ぶ辺があるとき true、そうでないとき false

といった二次元配列を用いる方法もあります。しかし今回の問題では、この方法ではメモリ容量が $O(N^{2})$ 必要なので、MLE となってしまいます。

コード

注意点として、頂点の番号は問題文中では $1, 2, \dots, N$ となっていますが、ここでは 1 を引いて $0, 1, \dots, N-1$ となるようにします。

このように、0 から始めることを 0-indexed などと呼んだりします。

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

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;  // 0-indexed にする
        
        // 頂点 a の隣接リストに b を追加する
        G[a].push_back(b);
        
        // 頂点 b の隣接リストに a を追加する
        G[b].push_back(a);
    }
    
    // 各頂点に隣接する頂点集合を出力していく
    for (int v = 0; v < N; ++v) {
        // 隣接する頂点のリストは G[v] と表せる
        // 小さい順に並び替える
        sort(G[v].begin(), G[v].end());
        
        // まず隣接リストのサイズを出力する
        cout << G[v].size() << " ";
        
        // 隣接リストの頂点を順に出力する
        for (auto v2 : G[v]) cout << v2+1 << " ";
        cout << endl;
    }
}