kmjp's blog

競技プログラミング参加記です

UTPC 2014 : C - 最小カットと最大カット

タイトルは無視した方が良い。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_c

問題

N頂点N無向辺からなるグラフが与えられる。
各頂点を赤か青に塗る。ただし各色最低1回は用いないといけない。

様々な塗り分け方をしたとき、辺の両端の点が異なる色の数について、最小値・最大値を求めよ。

解法

N頂点N無向辺なので、1つだけ閉路があるグラフとなる。

まず最小値から。
次数が1の点があれば、そこだけ赤にしてあとは青にすれば良く、最小値は1。
全体が1つの閉路となる場合だけ次数がないので、最小値は2になる。

最大値については、隣接する頂点を赤・青…と交互に塗っていけば、全辺で両端の色を分けられるので最大値はN。
ただし、閉路の長さが奇数の時だけは1か所同じ色が続いてしまうので最大値は(N-1)。

どちらも閉路の長さをDFSで求めれば判断できる。

int N;
int D[101000];
vector<int> E[101000];
int ng,ml;

void dfs(int cur,int dep) {
	int i;
	D[cur]=dep;
	FORR(r,E[cur]) {
		if(D[r]==-1) dfs(r,dep+1);
		else if(D[r]<D[cur]-1) ml=max(ml,(D[cur]+1-D[r]));
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	
	FOR(i,N) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	MINUS(D);
	dfs(0,0);
	
	_P("%d %d\n",1+(ml==N),N-(ml%2));
}

まとめ

閉路は適当にDFSで求めちゃったけど、もっといい方法あるのかな?