Codeforces #311 Div2 D. Vitaly and Cycle

なかなか面白かった。
http://codeforces.com/contest/557/problem/D

問題

N頂点M辺の無向グラフが与えられる。
ここにT辺を追加して奇数長の閉路を作りたい。

最小のTと、追加するT辺の組み合わせの数を求めよ。

解法

グラフが二部グラフを成す場合、奇数長の閉路ができない。
まずグラフが二部になるか判定しよう。
これはDFSで点を２色に塗り分けてもいいし、頂点を2*N個用意してUnion-Findを用いる方法もある。

最小３本辺を追加すれば長さ３の閉路ができるので、加える辺の長さは０～３の何れかである。

• 追加が０本のケース:
  • 二部グラフにならない連結成分があるとき、すでに奇数長の閉路があることになるので追加不要。
• 追加が１本のケース:
  • ２つ以上辺をもつ頂点がある場合、その点と隣接点２つの３点を選べば長さ３の閉路が作れるので、最小追加数は１本である。
  • 各連結成分において、点が白黒２色で塗り分けられてるものとする。
  • 連結成分内の点は当然連結しているので、白点同士の距離は元々偶数であり、白点を２つ選んで辺を追加すると奇数の閉路が作れる。黒点２点選ぶ場合も同様。
  • よって連結成分毎に白点２点または黒点２点を選ぶ選び方を列挙すればよい。
• 追加が３本のケース:
  • １本も辺がない場合、３点選んで３本辺を追加すればよいので通り。
• 追加が２本のケース:
  • 各頂点の次数が0～1の場合、各辺を跨ぐ２点と、その他の点を１個選べば三角形が作れる。
  • よってM*(N-2)通りの閉路が作れる。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<201010> uf;
ll N,M;
vector<int> E[101010];
int num[202020][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x].push_back(y);
		E[y].push_back(x);
		uf(x,y+N);
		uf(x+N,y);
	}
	
	FOR(x,N) if(uf[x]==uf[x+N]) return _P("0 1\n");
	if(M==0) return _P("3 %I64d\n",N*(N-1)*(N-2)/6);
	
	FOR(i,2*N) {
		if((i<N)^(uf[i]<N)) num[uf[i]][0]++;
		else num[uf[i]][1]++;
	}
	
	ll ret=0;
	FOR(i,2*N) if(num[i][0]+num[i][1]>=3) ret += (1LL*num[i][0]*(num[i][0]-1)+1LL*num[i][1]*(num[i][1]-1))/2;
	if(ret) return _P("1 %I64d\n",ret/2);
	
	_P("2 %I64d\n",M*(N-2));
	
}

まとめ

ちょっと頭をひねる問題でした。