TopCoder SRM 648 Div2 Medium Fragile2

SRM648は不参加。
仮に出てたら、Easy早解きMedium時間切れでレート維持かな…。
http://community.topcoder.com/stat?c=problem_statement&pm=13648

問題

N頂点の有効グラフが与えられる。
articulation pairとは２つの異なる頂点の対で、その２点を除くとグラフの連結数が変化するものをいう。
articulation pairの数を求めよ。

解法

特にひっかけの無い実装問題。
２つの頂点対を総当たりし、Union-FindなりWarshall-Floyedで連結数を数えればよい。

総当たり＋Warshall-FloyedでO(N^5)で間に合う。

int mat[21][21];

class Fragile2 {
	public:
	int N;
	int numcom(int x,int y) {
		int i,j,k;
		int vis[21]={};
		int comp=0;
		FOR(i,N) FOR(j,N) FOR(k,N) mat[j][k] |= mat[j][i]&&mat[i][k];
		FOR(i,N) if(vis[i]==0) {
			if(i==x) continue;
			if(i==y) continue;
			comp++;
			vis[i]=1;
			FOR(j,N) if(mat[i][j]) vis[j]=1;
		}
		return comp;
	}
	
	int countPairs(vector <string> graph) {
		int num,i,j,x,y,ret=0;
		N=graph.size();
		FOR(i,N) FOR(j,N) mat[i][j]=graph[i][j]=='Y';
		int b=numcom(-1,-1);
		FOR(y,N) FOR(x,y) {
			FOR(i,N) FOR(j,N) mat[i][j]=graph[i][j]=='Y';
			FOR(i,N) mat[i][x]=mat[x][i]=mat[y][i]=mat[i][y]=0;
			if(numcom(x,y)>b) ret++;
		}
		return ret;
		
	}
}

まとめ

Div2Mediumとしてはだいぶストレートな問題。