// --------------------------------------------------------------------
// Grid Challenge 2006 用 練習問題作成プログラム
//                                                2006/02/01
// by 東京大学大学院新領域創成科学研究科基盤情報学専攻 1年 吉田仁
// --------------------------------------------------------------------
// Copyright 2006 YOSHIDA Hitoshi
// --------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// [0,1) の乱数を返すマクロ
#define DRANDOM (random() * (1.0 / 2147483648.0))

int usage(char* argv[])
{
  fprintf(stderr, "$ %s <number of nodes> <average number of connections>\n",
	  argv[0]);
  return 1;
}

int main(int argc, char* argv[])
{
  char* connect = NULL;     // ノード間の接続を保持する配列
  int* conCount = NULL;     // ノードからの接続数を保持する配列
  int nNode = 0;            // ノード数
  double avgConnect = 0.0;  // 平均接続数
  int limConnect;           // 総接続本数
  int i, j;

  if( argc < 3 ) return usage(argv);
  nNode = strtol(argv[1], NULL, 10);
  avgConnect = strtod(argv[2], NULL);
  if( nNode < 2 || avgConnect < 0.0 || nNode < avgConnect )
    return usage(argv);

  // メモリ空間の確保
  connect = (char*)malloc(sizeof(char) * nNode * nNode);
  if( connect == NULL ) {
    fprintf(stderr, "Cannot allocate for connect[]\n");
    return 1;
  }
  conCount = (int*)malloc(sizeof(int) * nNode);
  if( conCount == NULL ) {
    fprintf(stderr, "Cannot allocate for conCount[]\n");
    free(connect);
    return 1;
  }
  for( i = 0 ; i < nNode * nNode ; i++ ) connect[i] = 0;
  for( i = 0 ; i < nNode ; i++ ) conCount[i] = 0;

  srandom(time(NULL)); // 乱数系列をバラす
  // 接続関係の設定
  limConnect = nNode * avgConnect * 0.5;
  for( i = 0 ; i < limConnect ; i++ ) {
    int sNode, eNode;
    do {
      sNode = (int)(DRANDOM * nNode);
      eNode = (int)(DRANDOM * (nNode - 1));
      if( sNode == eNode ) eNode = nNode - 1; // １つのノードでの接続を回避
    } while( connect[sNode * nNode + eNode] ); // 同じ接続を回避
    connect[sNode * nNode + eNode] = 1;
    connect[eNode * nNode + sNode] = 1; // 対称配置
    conCount[sNode]++;
    conCount[eNode]++;
  }

  // 表示(標準出力に出力)
  for( i = 0 ; i < nNode ; i++ ) {
    printf("%4d (%.6f,%.6f)%4d ", i + 1, DRANDOM, DRANDOM, conCount[i]);
    for( j = 0 ; j < nNode ; j++ ) {
      if( connect[i * nNode + j] ) {
	printf(" %d", j + 1);
      }
    }
    puts("");
  }

  return 0;
}