UTPC2013 C 直径

問題

日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_03）

二つの重みなし無向グラフが与えられるので、
それを一本の辺でつなぐとき、

• できたグラフの直径を最小にするようにつないだときの直径
• できたグラフの直径を最大にするようにつないだときの直径

をそれぞれ出力せよ。

制約条件

それぞれの頂点数≦1000
それぞれの辺数≦10000

方針

重みなしグラフなので、グラフの直径は全ての頂点から毎回幅優先をする
O(n * m)で間に合う。

これで、最大の直径をもつところの始点同士をつなぐ、
最小の直径をもつところの始点同士をつなぐ、
とするのがベストなつなぎかた。

で、つないだ後でもう一回直径を求めればいい。
幅優先しなおして求めなくて計算で求められるのだけど、コーナーケースがあるので危険。
Aの直径 + Bの直径 + 1とかになるが、最小同士をつないだ値は、元の直径未満になってしまうことがあるので、その場合もとの直径の大きい方を答えなければならない。

ソースコード

bool v[1000];
 
pi diameter(){
	int n, m;
	cin >> n >> m;
	vector<vi> e(n);
	rep(i, m){
		int a, b;
		cin >> a >> b;
		e[a].pb(b);
		e[b].pb(a);
	}
	int mx = 0, mn = inf;
	rep(i, n){
		memset(v, 0, sizeof(v));
		queue<pi> q;
		q.push(mp(i, 0));
		
		int dist = 0;
		
		while(!q.empty()){
			int c = q.front().first, co = q.front().second; q.pop();
			if(v[c]) continue;
			v[c] = 1;
			dist = max(dist, co);
			
			rep(j, e[c].size()){
				int to = e[c][j];
				if(!v[to]) q.push(mp(to, co + 1));
			}
		}
		mx = max(mx, dist);
		mn = min(mn, dist);
	}
	
	return mp(mx, mn);
}
 
int main(){
	pi a = diameter();
	pi b = diameter();
	//dbg(a); dbg(b);
	cout << max(max(a.first, b.first), a.second + b.second + 1) << " "
	<< a.first + b.first + 1 << endl;
	
	return 0;
}