TopCoder SRM 608, Division 2, Level 3 : BigOEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13002&rd=15841

問題概要

　有向グラフ が与えられる。このグラフ上の長さ L の歩道について考える。L が大きくなったとき、歩道の数のオーダーを L の多項式で表せるか求めよ。表せる場合は "Bounded" 、そうでない場合は "Unbounded" を返せ。
　歩道とは、頂点の羅列 v であって、有効な i について となるものを指す。

解法

　"Unbounded" となるための条件について考えます。L が十分に大きくなったときに歩道が存在しなければなりませんが、頂点数が有限であることを考えると、閉路上を周回することでしか実現できません。閉路が一つの場合、始点をずらすことでしか歩道の数を増やせないので、これでは多項式オーダーのままです。閉路が複数あったとしても行き来できなければ係数に閉路の数が掛かるだけで、まだ多項式オーダーのままです。従って、"Unbounded" になり得るのは、互いに行き来できる複数の閉路が存在する場合です。このときに限り、途中で枝分かれしてまた戻ってくる遷移によって、歩道の数を指数オーダーで増やすことができます。
　では、互いに行き来できる歩道の存在判定をするにはどうすればよいでしょうか？　行き来できる二つの閉路が存在するとすると、分岐点となる頂点 v が存在するはずです。v から遷移できる二つの頂点 u1, u2 であって、u1 と u2 のどちらからも v に到達できるとき、v は分岐点であると言えます。そのような v が存在すれば、v で枝分かれしてまた v に戻ってきて枝分かれして……という具合に歩道の数を増やせます。
　行き来できる閉路を検出するために必要な情報は、任意の頂点対に関する到達可能性です。これの計算は、Warshall-Floyd 法を

• dp[ i ][ j ] := i から j に到達できるか（ bool 値）

を更新するようにアレンジすることで可能です。分岐点候補となる頂点を全て試し、その遷移先の頂点であって分岐点候補に戻ってこれるものが複数存在するときはその点は分岐点です。すなわち、頂点 v について、

• graph[ v ][ i ] == 'Y' || dp[ v ][ i ] && dp[ i ][ v ]

を満たす i が複数存在すれば v は分岐点です。分岐点が存在するときに限り "Unbounded" が解となり、一つも見つからなければ "Bounded" が解です。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class BigOEasy
{
public:
	string isBounded( vector <string> graph )
	{
		const int N = graph.size();

		VVI dp( 50, VI( 50, false ) );
		REP( k, 0, N )
		{
			REP( i, 0, N )
			{
				REP( j, 0, N )
				{
					dp[i][j] |= graph[i][j] == 'Y' || dp[i][k] && dp[k][j];
				}
			}
		}

		REP( i, 0, N )
		{
			int cnt = 0;
			REP( j, 0, N )
			{
				cnt += graph[i][j] == 'Y' && dp[i][j] && dp[j][i];
			}

			if ( 2 <= cnt )
			{
				return "Unbounded";
			}
		}
		return "Bounded";
	}
};