SRM 441 Div1 Medium StrangeCountry

問題概要

N個の都市からなる国がある。
いくつかの都市の間には双方向に通行可能な道路が走っている。

次のような操作を何度か行うことにより任意の2つの都市を（直接または間接に）行き来できるようにしたい。
直接道路で結ばれている都市A,Bと直接道路で結ばれている都市C,Dを選ぶ。
A-Bの道路C-Dの道路を壊し、A-DとB-C間に、もしくはA-C,B-D間に新たに道路を作る。

この操作を最低何回行えば任意の2つの都市は行き来可能になるか求めよ。
不可能な場合は-1を出力せよ。

制約条件

グラフは隣接行列の形で与えられる。N≦50

方針

辺の数がN-1本がグラフが連結になる（この場合木になる）ため必要な最低の本数。

N-1本以上なら、次のように繰り返し操作を行うことで、グラフが連結になることがわかる。
二つの連結成分A,Bを取る。
Aの辺の数はAの頂点の数以上として一般性を失わない。
（要するに辺があまっている連結成分をAとする。）
するとAには必ずループがあるはずなので、ループで隣合う頂点をv1,v2とでもすれば、
Bの適当な2頂点とv1,v2について辺の組み換えを行うと、
A,B全体が連結になる。（v1,v2はループだったので別のパスでつながっているから）

ただしコーナーケースがあり、連結成分として孤立点があった場合、
辺の組み換えができないので、どうやっても全体を連結にすることができなくなる。

以上をまとめると次のように判別すればいいことがわかる。
辺の数がN-1本未満なら不可能。
孤立点があっても不可能。
そのどちらでもないときは可能。

ソースコード

int n, e[50][50];
bool v[50];
void dfs(int c){
	v[c]=1;
	rep(i,n)if(e[c][i]&&!v[i])dfs(i);
}

class StrangeCountry {
	public:
	int transform(vector <string> g) 
	{
		n=g.size();
		int edge=0;
		rep(i,n)rep(j,n){
			e[i][j]=g[i][j]=='Y';
			if(e[i][j])edge++;
		}
		if(edge/2<n-1)return -1;
		rep(i,n){
			bool ok=0;
			rep(j,n)if(e[i][j])ok=1;
			if(!ok)return -1;
		}
		
		rep(i,n)v[i]=0;
		int ans=-1;
		rep(i,n)if(!v[i]){
			ans++; dfs(i);
		}
		return ans;
	}
};