Codeforces Round #25 (Div 2 only) D. Roads not only in Berland

問題

n個の都市のうちいくつかがn-1本の双方向に通行可能な道路により結ばれている。
1日ごとに、1つ道路を壊し、新たな道路を1つ好きな都市と都市を結ぶように作ることができる。
全ての都市が行き来できるようになるまでにかかる最短の日数と、道路の作り方と壊し方を求めよ。

n≦1000を満たす。

解法1

ループの検出には定石があるようだ。
深さ優先探索において、探索中のノードをcnt[i]=1としておく。
探索中に、更に探索中のノードを見つけたら、それはループを検出したことになる。
再帰から帰ってきたら、自分のcntを2にする。

ソースコード

int n,cnt[1000];
vi shima;
vector<vi> e;
vector<pi> ans;

void rec(int c,int p)
{
	cnt[c]=1;
	fr(i,e[c])if(*i!=p)
	{
		if(cnt[*i]==0)rec(*i,c);
		else if(cnt[*i]==1)ans.pb(mp(*i,c));
	}
	cnt[c]=2;
}

void run()
{
	cin>>n;
	e.clear(); e.resize(n);
	ans.clear(); shima.clear();
	rep(i,n-1)
	{
		int a,b; cin>>a>>b; a--; b--;
		e[a].pb(b); e[b].pb(a);
	}
	
	rep(i,n)cnt[i]=0;
	rep(i,n)if(!cnt[i])
	{
		shima.pb(i);
		rec(i,-1);
	}
	cout<<ans.size()<<endl;
	rep(i,ans.size())cout<<ans[i].first+1<<" "<<ans[i].second+1
	<<" "<<shima[i]+1<<" "<<shima[i+1]+1<<endl;
}

解法2.

Union-Findを用いても解くことができる。
最初に道路を読み込んで行く際に、aとbが既に同じグループに属していたら、それはループである。
そのような辺を全て覚えておき、それらをグループとグループを結ぶ辺に変更すればいい。

ソースコード

Codeforces落ちてたので後ほどAC確認してからうｐ.