live archive 5021 Tree Representation

Tree Representation

問題概要

木が与えられる。
木のノードには1からnまで名前が付いている。
エッジに重みはない。

以下の手順をノードが二つになるまで繰り返す。

1. 最小の葉ノードを選び消す
2. 今消したノードの親を記録する。

この処理を繰り返した記録がある。
木を復元せよ。

解法

まず、記録にないノードはすべて最初の時点で葉である。
それが、現時点で葉である可能性があるノードの厳密な集合である。
（残り二個まで消すので子をもっているなら必ず登場する）
そして、最初に消えるのはその集合の中で一番小さなノードである。
そして、そのノードの親が記録されているのである。
その親番号がそれ以降に存在していなければ、それは葉になったと考えてよい。
（再帰的に部分木においても先述の法則は成り立つ。）
それを繰り返せば、各ノードの親がわかり、木を復元することができる。

ソース

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<set>
#include<cassert>

#define REP(i, b, n) for(int i = b; i <(int)n; i++)
#define rep(i, n) REP(i, 0, n)
#define FOR(it, o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end();++it)


using namespace std;

int main(){
  int T;
  cin >> T;
  rep(tc, T){
    if(tc != 0)cout << endl;
    int n;
    cin >> n;
    int in[n];
    set<int> L;
    
    rep(i, n){
      L.insert(i+1);
    }
    rep(i, n-2){
      cin >> in[i];
      if(L.find(in[i]) != L.end())L.erase(L.find(in[i]));
    }
    int p[n+1];
    rep(i, n+1)p[i] = -1;
    int now = 0;
    while(1){
      int mini = *(L.begin());
      L.erase(L.begin());
      p[mini] = in[now];
      now++;
      if(now == n-2)break;
      bool last = true;
      REP(i, now, n-2){
	if(in[i] == in[now-1])last = false;
      }
      if(last)L.insert(in[now-1]);
    }
    vector<int> left;
    REP(i, 1, n+1){
      if(p[i] == -1){
	left.push_back(i);
      }
    }
    assert(left.size() == 2);
    p[left[0]] = left[1];
    set<int> res[n+1];
    REP(i, 1, n+1){
      if(p[i] == -1)continue;
      res[i].insert(p[i]);
      res[p[i]].insert(i);
    }
    REP(i, 1, n+1){
      cout << i ;//<< ' ';
      FOR(it, res[i]){
	cout << ' ' << *it;
      }
      cout << endl;
    }
  }
}