Codeforces 73 D. FreeDiv

問題

n個の都市とm本の道からなる、国がある。
道は双方向に通行可能である。

州とは、道により行き来できる都市の塊を言う。
都市と都市を結ぶトンネルを以下の条件を満たすように好きに掘ることができる。

• 一つの都市につながるトンネルは最大1本である。
• 一つの州につながるトンネルは最大k本である。

いま、トンネルを掘ることおよび、都市と都市の間に新たに道を作ることにより、全ての都市を行き来可能にしたい。
新たに作らねばならない道の本数の最小値は何本か、求めよ。

制約条件

n,m,k≦10^6

方針

k=1の場合だけ場合分け。
この場合、州には1本しかトンネルを作れない。
したがって州の数-2本の道を作る必要がある。

その他の場合、次のように考える。
ある州からはじめて、その州にトンネルを掘ることにより、
他の州をつなげられるだけつなぐ。
この操作を繰り返す。

すると、いくつかの、都市が一つのみからなる州が残る。

都市一つのみからなる州は、1本の道路をつかって、
最大2個、今までの州の塊につなぐことができる。

したがって、必要な道路の本数は、
上の操作を繰り返したあとで残った都市の数/2を小数点未満切り上げたもの。

ソースコード

int n,m,k;
bool v[1000000];
vector<vi> g;
map<int,int> cnt;

int dfs(int c){
	v[c]=1;
	int res=1;
	rep(i,g[c].size())if(!v[g[c][i]])res+=dfs(g[c][i]);
	return res;
}
void run()
{
	cin>>n>>m>>k;
	cnt.clear();
	g=vector<vi>(n);
	rep(i,m){
		int a,b; cin>>a>>b;
		g[--a].pb(--b);
		g[b].pb(a);
	}
	memset(v,0,sizeof(v));
	
	int island=0;
	rep(i,n)if(!v[i]){
		cnt[dfs(i)]++;
		island++;
	}
	
	if(k==1){
		cout<<max(0,island-2)<<endl;
		return;
	}
	
	map<int,int>::iterator it=--cnt.end();
	int hand=min(it->first,k);
	it->second--;
	
	for(;hand>0;it--){
		while(hand>0&&it->second>0){
			hand=hand-1+min(k,it->first)-1;
			it->second--;
		}
		if(it==cnt.begin())break;
	}
	cout<<cnt[1]/2+cnt[1]%2<<endl;
}