ALDS1_11_A問題 隣接リスト・隣接行列についての解法

ALDS1_11_A問題(難易度1)の解法についてまとめます。

問題

グラフ G=(V,E)
の表現方法には隣接リスト(adjacency list) による表現と隣接行列(adjacency matrices)による表現があります。

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

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

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

入力

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

u k v1 v2 ... vk

uは頂点の番号、k は u の出次数、v1v2...vk　は u に隣接する頂点の番号を示します。

出力

出力例に従い、G の隣接行列を出力してください。aij の間に１つの空白を入れてください。

制限

1≤n≤100

入力例

4
1 2 2 4
2 1 4
3 0
4 1 3

出力例

0 1 0 1
0 0 0 1
0 0 0 0
0 0 1 0

問題解説

隣接リストとして与えられた、数値を隣接行列に直して出力する問題です。
隣接リストや隣接行列を知らなくとも、解説にどういうものかが書いてあるので、
知らなくとも解くことができます。

制約にNについて100以下であると定義されているので、動的に領域を確保しなくとも、
N分の配列を用意し、隣接行列として利用し、そのまま出力に利用することができます。

隣接行列についてはこちらにまとめました。

解法のコツ

動的に要素を受け取る方法

入力を受け取る際に、

k v1 v2 ... vk

とkの数に従い動的に入力を受け取る箇所があります。
これをc++で書くと以下のようになります。

    int n,u,k,v;
  
    cin >> n;
    // nの個数分回す
    for(int i = 0;i < n;++i){
        // 一旦Kを受け取る
        cin >> u >> k;
        u--;
        // 頂点の数だけ回す
        for(int j = 0;j < k;++j){
            cin >> v;
        }
    }

あとは、問題に書いてあることをそのまま出力すればokです。

c++での解法

#include

using namespace std;

#define N 100

int M[N][N];

int main(){
    int n,u,k,v;
  
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> u >> k;
        // 頂点を移動する
        u--;
        // 頂点の数だけ回す
        for(int j = 0;j < k;++j){
            cin >> v;
            --v;    // ずらす
            M[u][v] = 1;
        }
    }
    
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            // 2個目からは空白が必要
            if(j){
                cout << " ";
            }
            cout << M[i][j];
        }
        cout << endl;
    }
    
    return 0;
}