Codeforces #143 Div.2 E - Cactus

問題文 : Cactus

解法 :
答えは2^(パスs -> tまでの中にあるサイクルの数)になる(図を描いて考察すると分かる.)
よって、サイクルを検出して、それを1つの頂点に圧縮する.

頂点に圧縮する際に、根付き木にグラフを再構築すると, sとtのLCAをpとしておき
s->pのサイクルの数+t->pのサイクルの数が求めるサイクルの数になるので、前準備をしておけば,各クエリにlogN時間で応答することが出来る.

ゆえに, O((M+Q)logN)時間でプログラムが動作する.

※閉路検出などのテクニックは@kyuridenamidaさんに教わりました. この場を借りてお礼を申し上げます.

コード :

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define MAX_N (100000)
#define MAX_M (100000)

struct Edge {
	int from, to, id;
	Edge(int from, int to, int id) : from(from), to(to), id(id) {}
	Edge() {}
};

Edge cont[MAX_N];
vector<Edge> G[MAX_N];

int ppar[MAX_N], pdep[MAX_N];
int gr[MAX_N];
bool vis[MAX_N];
bool used[MAX_M];
bool loop[MAX_N];

void makeTree(int v)
{
	vis[v] = true;
	
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i].to]){
			used[G[v][i].id] = true;
			ppar[G[v][i].to] = v;
			pdep[G[v][i].to] = pdep[v] + 1;
			makeTree(G[v][i].to);
		}
	}
}

int depth[MAX_N];
int par[20][MAX_N];
int num[20][MAX_N];

vector<int> getCycle(int a, int b)
{
	vector<int> ret;
	if (pdep[a] < pdep[b]) swap(a, b);
	while (pdep[a] > pdep[b]){
		ret.push_back(a);
		a = ppar[a];
	}
	
	while (a != b){
		ret.push_back(a), ret.push_back(b);
		a = ppar[a], b = ppar[b];
	}
	ret.push_back(a);
	
	return (ret);
}

void dfs(int v)
{
	vis[v] = true;
	
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i].to]){
			depth[G[v][i].to] = depth[v] + 1;
			par[0][G[v][i].to] = v;
			num[0][G[v][i].to] = loop[G[v][i].to];
			dfs(G[v][i].to);
		}
	}
}

void initLCA()
{
	for (int i = 1; i < 20; i++){
		for (int j = 0; j < MAX_N; j++){
			if (~par[i - 1][j]){
				par[i][j] = par[i - 1][par[i - 1][j]];
				num[i][j] = num[i - 1][par[i - 1][j]] + num[i - 1][j];
			}
		}
	}
}

int countCycle(int a, int b)
{
	int ret = 0;
	if (depth[a] < depth[b]) swap(a, b);
	
	for (int i = 19; i >= 0; i--){
		if ((depth[a] - depth[b]) >> i & 1){
			ret += num[i][a];
			a = par[i][a];
		}
	}
	
	if (a == b) return (ret + num[0][a]);
	
	for (int i = 19; i >= 0; i--){
		if (par[i][a] != par[i][b]){
			ret += num[i][a];
			ret += num[i][b];
			a = par[i][a];
			b = par[i][b];
		}
	}
	ret += num[0][a] + num[0][b];
	a = par[0][a];
	
	return (ret + num[0][a]);
}

int main()
{
	int N, M;
	int two[MAX_N];
	
	two[0] = 1;
	for (int i = 1; i < MAX_N; i++){
		two[i] = (2 * two[i - 1]) % 1000000007;
	}
	
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < M; i++){
		scanf("%d %d", &cont[i].from, &cont[i].to);
		cont[i].id = i;
		G[--cont[i].from].push_back(Edge(cont[i].from, --cont[i].to, cont[i].id));
		G[cont[i].to].push_back(Edge(cont[i].to, cont[i].from, cont[i].id));
	}
	
	makeTree(0);
	
	memset(gr, -1, sizeof(gr));
	
	int idx = 0;
	for (int i = 0; i < M; i++){
		if (used[i] == false){
			vector<int> group = getCycle(cont[i].from, cont[i].to);
			for (int i = 0; i < group.size(); i++){
				gr[group[i]] = idx;
			}
			loop[idx++] = true;
		}
	}
	
	for (int i = 0; i < N; i++){
		if (gr[i] == -1){
			gr[i] = idx++;
		}
		G[i].clear();
	}
	
	for (int i = 0; i < M; i++){
		int a = gr[cont[i].from], b = gr[cont[i].to];
		G[a].push_back(Edge(a, b, i));
		G[b].push_back(Edge(b, a, i));
	}
	memset(par, -1, sizeof(par));
	memset(vis, 0, sizeof(vis));
	
	num[0][0] = loop[0];
	dfs(0);
	
	int Q;
	initLCA();
	scanf("%d", &Q);
	
	for (int i = 0; i < Q; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		printf("%d\n", two[countCycle(gr[--a], gr[--b])]);
	}
	
	return (0);
}