TopCoder SRM 691 Div2 Medium Sunnygraphs2

また0完した。めきめきレートが下がる。
今回はDiv2 Mediumも難しめなので一応ブログに記載。
https://community.topcoder.com/stat?c=problem_statement&pm=14302

問題

0～(N-1)番のN頂点の無向グラフがある。
i番の頂点はA[i]番の頂点と辺を結んでいる。(２頂点間に２つ辺があるケースもある)

ここでN番の頂点を新設する。
N頂点のうち一部のx番の頂点に対し、x番とA[x]番間の辺を消し、代わりにx番とN番を辺で結ぶということを行う。
全部で2^N通りの頂点選択法に対し、0～(N-1)番の頂点が連結する組み合わせ数を求めよ。

解法

全体が連結の場合、1点も選択しないケースは条件を満たす。
非連結なら条件を満たさない。

それ以外の場合、最低１点は選択されるので、それらの頂点はN番と連結する。
このケースで他の全頂点もN番と連結するかを考える。

i番とA[i]番の辺は無向辺だが、これを有向辺と見なそう。
各連結成分に対し、必ず閉路を成す頂点群が存在する。
閉路内の頂点群が最低1点選択されている場合、それらの連結成分は皆N番に到達可能である。
閉路外の頂点はどちらでも良い。

よって１つの閉路中の頂点群Vごとに(2^|V|-1)を掛け合わせ、あとは閉路を成さない頂点についてはその数だけ組み合わせを倍にしよう。
最後に、最初に書いた全体連結の分を1加算するとそれが解。

int mat[51][51];
int did[51];

class Sunnygraphs2 {
	public:
	long long count(vector <int> a) {
		int i,x,y,z;
		int N=a.size();
		ZERO(mat);
		FOR(i,N) mat[i][a[i]]=mat[i][i]=1;
		FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y] |= mat[x][z] & mat[z][y];
		
		ll ret=0;
		// con?
		FOR(x,N) FOR(y,N) if(x!=y) {
			int ok=0;
			FOR(z,N) if(mat[x][z] && mat[y][z]) ok=1;
			ret &= ok;
		}
		ZERO(did);
		ll r2=1;
		FOR(x,N) if(did[x]==0) {
			int inloop=0;
			FOR(y,N) if(mat[x][y] && mat[y][x]) inloop++;
			if(inloop==1) {
				r2 *= 2;
				did[x]=1;
			}
			else {
				r2 *= (1LL<<inloop)-1;
				FOR(y,N) if(mat[x][y] && mat[y][x]) did[y]=1;
			}
		}
		return ret+r2;
	}
}

まとめ

Div2 Mediumにしては難しくない？
これこそDiv1 Easyでいいよ…。