TopCoder, Single Round Match 650, Division 2, Level 3 : TheKingsRoadsDiv2

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13667&rd=16314

問題概要

　正整数 と，頂点数・辺数が共に の無向グラフが与えられる．辺の情報は 2 つの配列 で与えられ，各 に対し，2 頂点 を結ぶ辺が存在する．
　このグラフから辺を 1 つ削除することによって完全二分木を得ることができるか？
　

解法

　頂点数 を と書きます．
　 の制約から，頂点及び辺の数は 未満となります．1 つの辺を削除する方法も 1024 通り未満なので，辺を削除したグラフが完全二分木であるか否かをある程度高速に判定できれば，作れる全てのグラフについて判定を行うことで問題を解くことができます．
　では，与えられたグラフが高さ の完全二分木であるかを判定する方法を考えます．グラフが高さ の完全二分木であるとは，

• 連結で，かつ閉路が無い（木の定義）

であることに加えて，

• 次数が 2 の頂点が丁度 1 つ存在して，その頂点が根
• 任意の頂点について，次数が 3 以下
• 深さ （根の深さを 0 とする）に対して，その深さの頂点数は
• 任意の頂点について，0-based での深さは 未満

といった特徴があります（もしかしたら余計なの混ざってるかも）．閉路の検出は，DFS をしたとき同じ頂点を 2 度以上通るか否かで判定できます．また，その他の条件についても，DFS を根（次数 2 の頂点を根とする）から始めるようにして，深さをもちながら探索することで深さ毎の頂点数のカウントと，その他の条件の判定ができます．
　頂点数及び辺数が共に 本のグラフの DFS なので，この DFS は 時間でできます．辺を削除する方法は 通りだったので，全体では 時間となります．

コード

using VI = vector< int >;
using VVI = vector< vector< int > >;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back

class TheKingsRoadsDiv2
{
public:
	string getAnswer( int h, vector <int> a, vector <int> b )
	{
		{
			auto f = bind( minus< int >(), _1, 1 );
			transform( ALL( a ), a.begin(), f );
			transform( ALL( b ), b.begin(), f );
		}

		const int N = ( 1 << h ) - 1;
		const int M = SZ( a );

		REP( i, M )
		{
			VVI G( N );
			REP( j, M )
			{
				if ( i == j )
				{
					continue;
				}
				G[ a[j] ].PB( b[j] );
				G[ b[j] ].PB( a[j] );
			}

			VI visited( N ), counts( h );
			iota( ALL( counts ), 0 );
			transform( ALL( counts ), counts.begin(), []( const int c ){ return 1 << c; } );

			const auto root = find_if( ALL( G ), []( const VI &es ){ return SZ( es ) == 2; } );

			if ( root != G.end()
					&& dfs( G, visited, counts, root - G.begin() )
					&& all_of( ALL( counts ), bind( equal_to< int >(), 0, _1 ) ) )
			{
				return "Correct";
			}
		}

		return "Incorrect";
	}

	bool dfs( const VVI &G, VI &visited, VI &counts, const int u, const int p = -1, const int d = 0 )
	{
		if ( 3 < SZ( G[u] ) || SZ( counts ) <= d )
		{
			return false;
		}

		visited[u] = 1;
		--counts[d];

		FOR( v, G[u] )
		{
			if ( v == p )
			{
				continue;
			}
			if ( visited[v] || !dfs( G, visited, counts, v, u, d + 1 ) )
			{
				return false;
			}
		}

		return true;
	}
};