タイトルは無視した方が良い。
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で求めちゃったけど、もっといい方法あるのかな?