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; }