STEP 5.1 モデル木 (分枝数b, 最大の深さm) の 接続行列

<背景> 根(ルート)をノード番号0とする。ルートしかない木は深さ0とする。



Sドライブにある実行ファイルmodel-tree.exeは、b, mを引数とするモデル木について、以下のような情報を生成、出力する。

model-tree 2 3

# BF: 2, MD: 3
# Tree Size 15
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14

(最初の2行は、制御用の情報です。3行目からが接続行列のデータ)

この出力からは、ノード4からは、ノード9, 10が接続していることを読み取れる。



<問題> model-tree.exeの接続行列データ出力をパイプで受け取り、接続行列を出力せよ。また、引数のノードから接続しているノードをプリントせよ。

<実行例>

model-tree 2 3 | matrix 4
     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
  0  .  1  1  .  .  .  .  .  .  .  .  .  .  .  .
  1  .  .  .  1  1  .  .  .  .  .  .  .  .  .  .
  2  .  .  .  .  .  1  1  .  .  .  .  .  .  .  .
  3  .  .  .  .  .  .  .  1  1  .  .  .  .  .  .
  4  .  .  .  .  .  .  .  .  .  1  1  .  .  .  .
  5  .  .  .  .  .  .  .  .  .  .  .  1  1  .  .
  6  .  .  .  .  .  .  .  .  .  .  .  .  .  1  1
  7  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  8  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  9  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 10  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 11  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 13  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 14  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
4: 9 10


<下のプログラムに適切に追加しなさい。上とは異なる実行例で確認してください>


解答例
#include <stdio.h>
#include <stdlib.h>

/* 格納可能なノード最大値 */
#define NMAX 0xFFF

/* プロトタイプ */
void initAdj(void); /* adjacency 隣接 */
void printAdj(void);

int adj[NMAX][NMAX]; /* 確保。かなり大きい */
int nmax; /* 実際のモデル木の最大ノード */

/* 接続行列の初期化 */
void initAdj() {

   int i,j;
   int bf, md; /* bとmの値 */

   /* 最初の2行の制御用情報から、読み込み */
   scanf("# BF: %d, MD: %d\n", &bf, &md);
   scanf("# Tree Size %d\n", &nmax);

   /* 使用する部分に0をセット */
   for (i = 0; i < nmax; i++)
       for (j = 0; j < nmax; j++) 
           adj[i][j]=0;
 
   /* 3行目から、2つずつのデータを読み込む。最後はEOF。例題0101では、control z(UNIXはcontrol d) */
   while (scanf("%d %d", &i, &j)!=EOF) {
       if (i < nmax && j < nmax) {
           adj[i][j]=1;
       }
    }
}

void printAdj(){
    int i,j;
  
    /* 以下を作成せよ  解答*/

    printf("   ");
    for (j = 0; j < nmax; j++)
        printf("%3d", j);

    printf("\n");
    for (i = 0; i < nmax; i++){
        printf("%3d", i);
        for (j = 0; j < nmax; j++)
            if (adj[i][j]) 
                 printf("  1");
            else 
                 printf("  .");
     printf("\n");
   }

}


int main(int argc, char *argv[]){
   int start, j;
 
   if (argc != 2){
      exit(0);
   }

   start = atoi(argv[1]);

   initAdj(); /* 初期化せよ。標準入力からデータを読み込み、セットせよ */
   printAdj(); /* 接続行列をプリント */

   printf("%d:", start);
   /* startノードに隣接しているノードを出力せよ 解答*/

   for (j = 0; j < nmax; j++){
       if(adj[start][j]) printf(" %d", j);
   }
   printf("\n");

   return 0;
}