TopCoder SRM 628, Division 2, Level 3 : InvariantSets

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13242&rd=16009

問題概要

　 内の整数からなる集合 と、 上の写像 がある。 は配列 によって表され、 である。
　また、 の部分集合 が invariant set であるとは、次の条件を満たすときである。

• 

　invariant set の総数を求めよ。

解法

　 の各要素を頂点、 による変換を有向辺としたグラフ を考えます。
　ある の要素を に加えるとき、グラフ上の対応する頂点から到達可能な頂点（に対応する の要素）も に加えなければなりません。このことを踏まえると、同じ強連結成分に属する頂点集合は、全て に加えるか、全く使わないかの二択になります。*1
　また、強連結成分という単位で考えると、無条件に に加えられる強連結成分は、出次数が 0 であるような強連結成分であることも分かります。さらに、ある強連結成分を に加えたとき、そこに接続する強連結成分に関して、それを に加えるか否かの選択が可能になります。このことを言い換えて、「ある強連結成分を に加えたとき、その条件下では、そこに接続する強連結成分を自由に に加えることができる」と考えると、始点となった強連結成分の場合と同じように計算することができることが明確になります。
　以上のことから、 に加えるかどうかを選択し始められるのは出次数が 0 の強連結成分からで、ある強連結成分から作れる の総数は、それを使わない場合の 1 通りと、それを使う場合の選択肢の総数の和になります。使う場合に生じる選択肢の総数とは、そこに接続する強連結成分に関して選択肢の数を掛け合わせた値です。あとは、出次数 0 の強連結成分全てに関して、作れる部分集合の総数を掛け合わせれば全体の答えが求まります。

コード

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

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )

#define PB( n ) push_back( n )

// 強連結成分分解 / Strongly Connected Component
// O( |V| + |E| )
class StronglyConnectedComponents;
// stronglyconnectedcomponents( |V| )
// connect( from, to )
// solve() : 連結成分の数が返る
// componentNumbers() : 頂点番号→連結成分の番号 の表が返る
// 連結成分の番号の大小は、トポロジカル順序の大小と一致

class InvariantSets
{
public:
	long long countSets( vector <int> f )
	{
		const int N = f.size();

		StronglyConnectedComponents scc( N );
		REP( i, 0, N )
		{
			scc.connect( i, f[i] );
		}

		const int k = scc.solve();
		VI components = scc.componentNumbers();

		VVI G( k ), Gr( k );
		REP( i, 0, N )
		{
			if ( components[i] != components[ f[i] ] )
			{
				G[ components[i] ].PB( components[ f[i] ] );
				Gr[ components[ f[i] ] ].PB( components[ i ] );
			}
		}
		

		LL res = 1;
		REP( i, 0, k )
		{
			if ( G[i].empty() )
			{
				res *= rec( Gr, i );
			}
		}
		return res;
	}

	LL rec( const VVI &Gr, const int u )
	{
		LL res = 1;
		FOR( v, Gr[u] )
		{
			res *= rec( Gr, v );
		}
		return res + 1;
	}
};

*1:辺の張られ方を考えると要素数が 2 以上の強連結成分はただの閉路ですが、ライブラリを利用できることと、閉路でない部分も含めて統一的に扱えることから強連結成分として話を進めます