SRM 299 Div2-1000: StrangeParticles

keyword

有向グラフ　強連結成分分解　C++

問題概要

N(<50)個の粒子がある。2つの粒子が衝突したとき、どちらか片方が消滅することがある。任意の2粒子間で衝突が起こったときの結果が与えられる。好きな順に衝突を起こせるとき、最終的に粒子を何個まで減らせるか求める問題。

解法

xとyが衝突したときxが消滅するならxからyへ辺を張る。このようなグラフを強連結成分分解してDAGに落とす。sinkの個数が答えとなる。

int pars[100];
int getRoot(int x){
	return x==pars[x]?x:(pars[x]=getRoot(pars[x]));
}
int merge(int x, int y){
	return pars[getRoot(x)] = getRoot(y);
}

class StrangeParticles {
public:
int remain(vector <string> g) {
	for(int i=0; i<100; i++){
		pars[i] = i;
	}
	int N = g.size();
	for(int i=0; i<N; i++)for(int j=0; j<N; j++){
		if(g[i][j] == '+') g[i][j] = '-';
		else if(g[i][j] == '-') g[i][j] = '+';
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(g[i][j] == '+') g[i][j] = '0';
		}
	}
	for(int k=0; k<N; k++){
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++)if(g[i][k]=='-' && g[k][j]=='-'){
				g[i][j] = '-';
			}
		}
	}
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++)if(g[i][i] == '-' && g[j][j] == '-' && g[i]==g[j]){
			merge(i,j);
		}
	}
	for(int i=0; i<N; i++)for(int j=0; j<N; j++)if(j!=pars[j]){
		g[i][j] = '0';
	}
	for(int i=0; i<N; i++)g[i][i] = '0';
	int ret = 0;
	for(int i=0; i<N; i++)if(i==pars[i]){
		if(g[i] == string(N,'0')) ret++;
	}
	return ret;
}