AOJ 1236 : Map of Ninja House

問題リンク：Map of Ninja House | Aizu Online Judge

問題概要：
無向グラフが存在する
自分は最初そのグラフのノード番号０のノードにいる
入力が正のとき、それは今いるノードの次数を表す
入力が負のとき、それは（今いるノードの深さ）ー（１つ前にいたノードの深さ）を表す
ここで深さとは、ノード０からの距離を意味する
これらの入力からその無向グラフを復元せよ

解法：
今いる場所、これまでの部屋番号の最大値＋１の値、これまでに通った経路、
これまでの部屋の残りの次数、部屋の深さを記録する
入力の0番めだけは最初に処理しておく
それ以外は、
入力が正なら、新しい部屋を追加し、深さ等を更新する
入力が負なら、これまでに通った経路を後ろから順に見ていき、深さが正しいものをみつけたらそこと今の部屋をつなげる

これらの処理をした後に、今いる部屋の次数がいっぱいでない部屋になるまで部屋を戻っていく

コード：

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cassert>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 110

using namespace std;

vector<int> G[MAX];
int remain[MAX];
int depth[MAX];

int main(){
  int T;
  cin >> T;
  while(T--){

    for(int i=0;i<MAX;i++){
      G[i].clear();
      remain[i] = 0;
      depth[i] = -1;
    }
    vector<int> record;
    vector<int> input;

    int r,cur,upper;

    while(cin >> r,r){
      input.push_back(r);
    }

    remain[0] = input[0];
    cur = 0, upper = 1, depth[0] = 0;

    for(int i=1;i<input.size();i++){
      //cout << "the input => " << input[i] << endl;
      //cout << "i = " << i << " cur = " << cur << endl;
      if( input[i] > 0 ){

	G[cur].push_back(upper);
	G[upper].push_back(cur);
	depth[upper] = depth[cur] + 1;
	remain[upper] = input[i] - 1;
	assert(remain[upper] >= 0);
	remain[cur]--;
	assert(remain[cur] >= 0);
	cur = upper++;

      } else {
	assert(depth[cur] != -1);
	int next = depth[cur] + input[i];
	for(int j=record.size()-1;j>=0;j--){
	  if(next == depth[record[j]]){
	    next = record[j];
	    break;
	  }
	}
	assert(next >= 0);
	G[next].push_back(cur);
	G[cur].push_back(next);
	remain[next]--;
	assert(remain[next] >= 0);
	remain[cur]--;
	assert(remain[cur] >= 0);

      }

      record.push_back(cur);

      for(int j=record.size()-1;j>=0;j--){
	if(remain[cur] != 0){
	  break;
	}
	cur = record[j];
      }
    }

    for(int i=0;i<upper;i++){
      cout << i+1;
      sort(G[i].begin(),G[i].end());
      for(int j=0;j<G[i].size();j++){
	cout << " " <<  G[i][j]+1;
      }
      cout << endl;
    }


  }
  return 0;
}