読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, Single Round Match 648, Division 2, Level 2 : Fragile2

問題概要

 N 頂点の(連結とは限らない)単純無向グラフが与えられる.グラフは N \times N の文字の行列 graph として与えられる.graph_{ij} が 'Y' のとき,2 頂点 i, j を結ぶ辺が存在することを表し,'N' のときその 2 点を結ぶ辺が無いことを表す.
 このグラフから 2 つの頂点を選ぶ選び方であって,選んだ 2 頂点を頂点集合から削除して得られる誘導部分グラフの連結成分の個数が,元のグラフのそれより増えるようなものの数を求めよ.
 N \leq 20

解法

 まずは元のグラフの連結成分の個数を求めることを考えます.最初,全ての頂点が異なる連結成分に属しているという状態を考えて,各辺について,その両端点が属する連結成分を統合していくことで,連結成分を求めることができます.この操作は,Union-Find を効率的に処理すれば,O( N^2 \alpha( N ) ) 時間で実行できます.(ここで \alpha(n) は,アッカーマン関数A(n) として,f(n) = A( n, n )逆関数です)
 さて,点を削除した場合の連結成分の個数も,もちろん同じ方法で求めることができます.その場合,2 点の選び方の総数は O( N^2 ) なので,そのそれぞれに対して連結成分を求めると,全体の計算量は O( N^4 \alpha( N ) となります.N の制約が小さいので,これで解くことができます.

コード

using VS = vector< string >;

#define REP2( i, n ) for ( int i = 0; i < ( int )( n ); ++i )
#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 SZ( v ) ( (int)( v ).size() )

class UnionFind; // 中身省略
// UnionFind( N )
// find( x )
// same( x, y )
// unite( x, y )
// groups()
// groupSize( x )

class Fragile2
{
public:
	int countPairs( vector <string> graph )
	{
		const int N = SZ( graph );
		const int orig = components( graph );

		int res = 0;
		REP( u, N )
		{
			REP( v, u )
			{
				VS G = graph;
				G.erase( G.begin() + u );
				G.erase( G.begin() + v );
				for_each( ALL( G ), bind( ( string&( string::* )( size_t, size_t ) )&string::erase, _1, u, 1 ) );
				for_each( ALL( G ), bind( ( string&( string::* )( size_t, size_t ) )&string::erase, _1, v, 1 ) );

				res += orig < components( G );
			}
		}
		return res;
	}

	int components( const VS &G )
	{
		const int V = SZ( G );
		UnionFind uf( V );

		REP( i, V )
		{
			REP( j, V )
			{
				if ( G[i][j] == 'Y' )
				{
					uf.unite( i, j );
				}
			}
		}

		return uf.groups();
	}
};