POI 2 Stage 1 Trees ( DFS )

http://main.edu.pl/en/archive/oi/2/drz

題意：
這裡限制樹的每個節點的兒節點必須是 0 或者 2，否則不稱做樹。
給編號由小到大的葉節點的深度，求樹是否存在，存在的話輸出每個節點的父節點編號，以及樹的括號序列表示。

資料規模：
In the first line of the standard input there is a positive number of the sequence elements (not greater than 2500). In the second line there are successive elements of the sequence separated by single spaces.

解法：
顯然可以貪心做，因為如果答案存在，一定是唯一的，當前的深度不足就必須往下走，足了就必須折返，空的必須補。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2500;

int N;
int A[ MAXN ];
map< int, int > par;

int cnt = 0;
string ans;
int X = 0;

void dfs( int fa, int d ){
  ans += "(";
  int u = ++cnt;
  par[ u ] = fa;
  if( d == A[ X ] ){
    ++X;
    ans += ")";
    return;
  }
  if( d > A[ X ] ){
    cout << "NIE\n";
    exit( 0 );
  }
  dfs( u, d + 1 );
  if( X == N ){
    cout << "NIE\n";
    exit( 0 );
  }
  dfs( u, d + 1 );
  ans += ")";
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  dfs( 0, 0 );
  if( X < N ){
    cout << "NIE\n";
    exit( 0 );
  }
  for( int i = 1; i <= cnt; ++i ){
    cout << par[ i ] << " \n"[ i == cnt ];
  }
  cout << ans << endl;
  return 0;
}