0w1

POI 2 Stage 3 Step Traversing a Tree ( DFS )

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

題意:
給一棵樹,求一個序列,可以不重複拜訪所有節點,而且相鄰節點距離不超過 3。

資料規模:
In the first line of the standard input there is a positive integer n, not greater than 5000 - it is the number of vertices of the tree.
In each of the following n - 1 lines there is one pair of positive integers separated by a single space and representing one edge of the tree.

解法:
考慮遞迴完成,考慮可以在某個子樹 u 完全未被拜訪的情況下,走完該子樹且結束在 u,稱該函數為 f( u )。只有 f() 函數是不夠的,所以考慮函數 g(),可以在子樹 u 未被拜訪的情況下,走完該子樹且開始在 u。接著就會發現深度為奇數的用 f(),偶數的用 g(),能保證是好的。

時間 / 空間複雜度:
O( N )

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

const int MAXN = 5000;

int N;
vector< int > G[ MAXN ];

void dfs( int u, int fa, vector< int > &ans, int st ){
  if( st ){
    ans.push_back( u );
  }
  for( int i = 0; i < G[ u ].size(); ++i ){
    int v = G[ u ][ i ];
    if( v == fa ) continue;
    dfs( v, u, ans, st ^ 1 );
  }
  if( not st ){
    ans.push_back( u );
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N - 1; ++i ){
    int u, v; cin >> u >> v; --u, --v;
    G[ u ].push_back( v );
    G[ v ].push_back( u );
  }
  vector< int > ans;
  dfs( 0, -1, ans, 0 );
  assert( ans.size() == N );
  for( int i = 0; i < N; ++i ){
    cout << ans[ i ] + 1 << "\n";
  }
  return 0;
}