グラフの表現

問題

実行時間制限: 1 sec / メモリ制限: 65536 KB
グラフ \(G = (V,E)\) の表現方法には隣接リストによる表現と隣接行列による表現がある。

隣接リスト表現では、 \(V\) の各頂点に対して \(1\) 個、合計 \(|V|\) 個のリスト \(Adj|V|\) でグラフを表す。頂点 \(u\) に対して、隣接リスト \(Adj[u]\) は \(E\) に属する辺 \((u,v_i)\) におけるすべての頂点 \(v_i\) を含んでいる。つまり、 \(Adj[u]\) は \(G\) において \(u\) と隣接するすべての頂点からなる。

一方、隣接行列表現では、頂点 \(i\) から頂点 \(j\) へ辺がある場合 \(a_{ij}\) が \(1\) 、ない場合 \(0\) であるような \(|V|×|V|\) の行列 \(A\) でグラフを表す。

隣接リスト表現の形式で与えられた有向グラフ \(G\) の隣接行列を出力するプログラムを作成せよ。 \(G\) は \(n = |V|\) 個の頂点を含み、それぞれ \(1\) から \(n\) までの番号がついている。

制約

  • \(1 \leqq n \leqq 100\)

入力

最初の行に \(G\) の頂点数 \(n\) が与えらえる。続く \(n\) 行で各頂点 \(u\) の隣接リスト \(Adj[u]\) が以下の形式で与えられる。

\(u \hspace{8px} k \hspace{8px} v_1 \hspace{8px} v_2 \hspace{8px} ... \hspace{8px} v_k\)

\(u\) は頂点の番号、\(k\) は \(u\) の出次数、 \(v_1 v_2 ... v_k\) は \(u\) に隣接する頂点の番号を示す。

出力

出力例のように、 \(G\) の隣接行列を出力せよ。 \(a_{ij}\) の間に \(1\) つの空白を入れること。

例1

入力

\(4\)
\(1 \hspace{8px} 2 \hspace{8px} 2 \hspace{8px} 4\)
\(2 \hspace{8px} 1 \hspace{8px} 4\)
\(3 \hspace{8px} 0\)
\(4 \hspace{8px} 1 \hspace{8px} 3\)

出力

\(0 \hspace{8px} 1 \hspace{8px} 0 \hspace{8px} 1\)
\(0 \hspace{8px} 0 \hspace{8px} 0 \hspace{8px} 1\)
\(0 \hspace{8px} 0 \hspace{8px} 0 \hspace{8px} 0\)
\(0 \hspace{8px} 0 \hspace{8px} 1 \hspace{8px} 0\)

【出典】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」269〜272頁

解答例(C++)

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

int main() {

  int n;
  cin >> n;

  int graph[n][n];

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      graph[i][j] = 0;
    }
  }

  for(int i = 0; i < n; i++) {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; j++) {
      int v;
      cin >> v;
      graph[u - 1][v - 1] = 1;
    }
  }

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      cout << graph[i][j] << " ";
    }
    cout << endl;
  }

  return 0;

}

グラフ構造の情報の持ち方

グラフは二次元配列で持つ。例えば、二次元配列を \(A\) とすると \(A[i][j]\) が頂点 \(i\) と頂点 \(j\) の関係を表す。無向グラフの隣接行列では、頂点 \(i\) と頂点 \(j\) の間に辺がある場合、\(A[i][j]\) と \(A[j][i]\) の値を \(1\) にする。辺がない場合は \(0\) とする。有向グラフの隣接行列では、頂点 \(i\) から頂点 \(j\) に向かって辺がある場合、\(A[i][j]\) の値を \(1\) にする。辺がない場合は \(0\) とする。