ICPC2017 Asia Regional Tsukuba K Counting Cycles

問題

n頂点m辺からなる連結な無向グラフが与えられる。そのグラフに含まれる単純閉路（同じ頂点を二度通らないような閉路）の個数を求めよ。

制約条件

n≦10万
m≦n+15

解法

まずループに関係ない部分は閉路の個数に関係ないので取り除く。次数1の頂点は全部取っていってしまっていい。
次にグラフを縮約する。長さ3以上のパスは長さ2にして間の頂点を取り除いてしまってもループの個数には関係ない。
（長さ2のパスを長さ1に圧縮するとループの個数は変化しないが、重複辺が出るので少しややこしいかもしれない。）

こうすると頂点数は50くらいまで減る。
実はこのグラフ上で単純に再帰でループを数える解法が通るっぽい。
再帰でループを数えるときには

• 重複をしないようにするため、最小の頂点番号を持つ
• 二通りの向きで数えないようにするため、最初の頂点から出た頂点と最初の頂点へ入る頂点で前者が大きいもののみを数える（または後者を数えるか、両方数えて２で割るか）

とすればよい。

想定解はサイクル基底を見つけて、サイクル基底k個を全て使うか使わないか2^k通りサイクルを作って、作ったサイクルが単純閉路になっているかを調べるというものらしい。
サイクル基底はXOR回廊で出たやつ。

木に16本まで辺を足したグラフなので、サイクル基底は16個以下。（なので単純閉路の個数も高々2^16個）
木に辺(a, b)を足したときできるサイクルaからbへのパスと辺(a, b)なので探索で簡単に求まる。
自分はこのときに各辺がどのサイクル基底に属するかの集合をbitで各辺にもたせた。

ソースコード

縮約の仕方が下手だったので実装は結構地獄だった。
次数１の頂点をキューに入れながら消せるだけ消す、次数２の頂点をキューに入れながら消せるだけ消す、などやるともう少し簡単に書けるっぽい。

void bridge(const vector<vi> &g, vector<pi> &hasi){
	int n = g.size(), cnt = 0;
	vi num(n, -1), low(n, inf);
	function<void(int,int)> rec = [&](int c, int p){
		num[c] = low[c] = cnt++;
		for(int i : g[c]) if(p != i){
			if(num[i] >= 0) low[c] = min(low[c], num[i]);
			else{
				rec(i, c);
				low[c] = min(low[c], low[i]);
				if(low[i] > num[c]) hasi.emplace_back(c, i);
			}
		}
	};
	rec(0, 0);
}

vector<vector<pi>> in(vector<pi> &es){
	int n, m; cin >> n >> m;
	vi p(n, -1);
	
	function<int(int)> root = [&](int x){
		if(p[x] < 0) return x;
		return p[x] = root(p[x]);
	};
	auto merge = [&](int a, int b){
		a = root(a); b = root(b);
		if(a == b) return 0;
		p[b] = a;
		return 1;
	};
	vector<vi> e(n + 1);
	vector<bool> mark(n + 1);
	rep(i, m){
		int a, b; cin >> a >> b; a--; b--;
		int loop_edge = !merge(a, b);
		if(loop_edge){
			es.emplace_back(a, b);
			mark[a] = mark[b] = 1;
		}
		else{
			e[a].pb(b);
			e[b].pb(a);
		}
	}
	//まず橋は全部消してよい
	{
		vector<vi> e2 = e;
		vector<pi> hasi;
		for(pi p : es){
			e2[p.first].pb(p.second);
			e2[p.second].pb(p.first);
		}
		bridge(e2, hasi);
		set<pi> hasis;
		for(auto p : hasi){
			hasis.insert(p);
			hasis.emplace(p.second, p.first);
		}
		rep(i, n){
			vi ee;
			for(int j : e[i]) if(!hasis.count(pi(i, j))) ee.pb(j);
			e[i] = ee;
		}
	}
	
	rep(i, n) if(e[i].size() > 2) mark[i] = 1;
	
	//縮約
	vector<bool> vis(n);
	vi v;
	function<void(int,int,int)> rec = [&](int c, int p, int cnt){
		if(!mark[c]) cnt++;
		else cnt = 0;
		
		v.pb(c);
		vis[c] = 1;
		for(auto i : e[c]) if(i != p){
			
			if(mark[i] && cnt > 1){
				int x = v[v.size() - cnt];
				for(vi::iterator j = e[x].begin(); j != e[x].end(); ++j) if(*j == v[v.size() - cnt + 1]){
					e[x].erase(j);
					break;
				}
				for(vi::iterator j = e[i].begin(); j != e[i].end(); ++j) if(*j == c){
					e[i].erase(j);
					break;
				}
				e[x].pb(i);
				e[i].pb(x);
			}
			if(!vis[i]) rec(i, c, cnt);
			if(!mark[c]) break;
		}
		v.pop_back();
	};
	rep(i, n) if(!vis[n] && mark[i]){
		v.clear();
		rec(i, i, 0);
	}
	
	//番号を圧縮
	int N = 0;
	vi to(n, -1);
	function<void(int)> dfs = [&](int c){
		to[c] = N++;
		for(auto i : e[c]) if(to[i] < 0) dfs(i);
	};
	rep(i, n) if(to[i] < 0 && mark[i]) dfs(i);
	
	vector<vector<pi>> g(N);
	rep(i, n) if(to[i] >= 0) for(int j : e[i]) if(to[j] >= 0){
		g[to[i]].emplace_back(to[j], 0);
	}
	for(auto &i : es) i = pi(to[i.first], to[i.second]);
	
	return g;
}

void run(){
	cin.tie(0); cin.sync_with_stdio(0);
	vector<pi> es;
	vector<vector<pi>> g = in(es);
	
	//サイクル基底の列挙
	vector<bool> vis(g.size());
	vector<pi*> stk;
	function<int(int,int,int,int)> find_loop = [&](int c, int s, int t, int id){
		vis[c] = 1;
		if(c == t){
			for(int i = (int)stk.size() - 1; i >= 0; i--) stk[i]->second |= 1 << id;
			return 1;
		}
		for(auto &i : g[c]){
			if(vis[i.first]) continue;
			stk.pb(&i);
			if(find_loop(i.first, s, t, id)) return 1;
			stk.pop_back();
		}
		return 0;
	};
	int m = es.size();
	rep(i, m){
		fill(all(vis), 0);
		stk.clear();
		int a = es[i].first, b = es[i].second;
		int res = find_loop(a, a, b, i);
	}
	rep(i, m){
		int a = es[i].first, b = es[i].second;
		g[a].emplace_back(b, 1 << i);
		g[b].emplace_back(a, 1 << i);
	}
	
	//逆辺にもフラグを立てる
	map<pi, pi*> tbl;
	rep(i, g.size()) for(auto &j : g[i]) tbl[pi(i, j.first)] = &j;
	rep(i, g.size()) for(auto &j : g[i]){
		int b = j.second | tbl[pi(j.first, i)]->second;
		j.second = tbl[pi(j.first, i)]->second = b;
	}
		
	//数える
	//dfsして連結かつループで誘導されるグラフの頂点が全て次数が2
	function<int(int,int)> dfs = [&](int c, int bit){
		vis[c] = 1;
		int deg = 0, res = 1;
		for(auto i : g[c]){
			if(__builtin_popcount(i.second & bit) % 2 == 0) continue;
			if(!vis[i.first]) res &= dfs(i.first, bit);
			deg++;
		}
		if(deg != 2) return 0;
		return res;
	};
	int ans = 0;
	rep(i, 1 << m){
		fill(all(vis), 0);
		int v = -1;
		rep(j, g.size()) for(pi k : g[j]) if(__builtin_popcount(k.second & i) % 2){
			v = j;
			break;
		}
		
		if(v < 0 || !dfs(v, i)) continue;
		rep(j, g.size()){
			bool f = 0;
			for(pi k : g[j]) if(__builtin_popcount(k.second & i) % 2){
				f = 1;
				break;
			}
			if(f != vis[j]) goto FAIL;
		}
		ans++;
		FAIL:;
	}
	cout << ans << endl;
}

int main(){
	run();
	return 0;
}