AtCoder蟻本 初級編 2-5 グラフ ①二部グラフ判定

CODE FESTIVAL 2017 qualB C - 3 Steps(500)

C - 3 Steps

概要

N頂点M辺の連結無向グラフに、「長さがちょうど3の経路をもつ2頂点間に辺を追加する」ということを繰り返す。追加できる辺の最大値を答えよ。

制約

2 ≦ N, M ≦ 10^5

方針

最終的に、奇数長の経路をもつ頂点間にはかならず辺が追加されることになる。
例えばa-b-c-d-e-f-g-hという頂点・辺があった場合にa-hを結ぶ辺が追加される様子をみる。
aからdはa-b-c-dで経路長3なので辺a-dが追加される。するとaからfはa-d-e-fで経路長3になるので辺a-fが追加される。そうするとaからhがa-f-g-hで経路長3になるため、めでたく辺が追加される。

よって、与えられたグラフにおいて、各頂点間の奇数経路長の経路の様子を確認する。
これは、2部グラフであるかどうかで様子がかわる。

2部グラフであるなら、頂点を2つのグループに分けることが出来る。このとき、同じグループに属する頂点同士は経路長が偶数であるため、辺が追加されることはない。逆に異なるグループに属する頂点同士は経路長が奇数であるため、頂点同士を結ぶ辺が追加される。

2部グラフでないなら、グラフは奇数長のサイクルを持つことになる。最短距離が偶数の2頂点は、このサイクルを通る経路を考えると奇数経路長の経路を作ることが出来るので、結局すべての頂点同士を結ぶ辺が追加される。

感想

2部グラフを説明したブログです。参考にさせていただきました。
prd-xxx.hateblo.jp

解答

Submission #5029642 - CODE FESTIVAL 2017 qual B

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int max_N = 100005;
 
ll N, M;
vector<int> colors(max_N, -1);
vector<vector<int>> g(max_N, vector<int>());
 
bool dfs(int v, int color){
	colors[v] = color;
 
	for(int x : g[v]){
		if(colors[x] == color) return false;
		if(colors[x] == -1 && !dfs(x, 1 - color)) return false;
	}
 
	return true;
}
 
bool is_bipartite(){
	return dfs(0, 1);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> M;
	rep(i, M){
		int a, b;
		cin >> a >> b;
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}
 
	if(is_bipartite()){
		ll cnt = 0;
		for(int i = 0; i < N; i++){
			if(colors[i] == 1) {
				cnt++;
			}
		}
 
		cout << (N - cnt) * cnt - M << endl;
	}else{
		cout << N * (N - 1) / 2 - M << endl;
	}
}