CodeForces 231E Cactus(边双缩点、LCA)

题意:

$给定一颗N\le 10^5个点的仙人掌,M\le 10^5条边$
$仙人掌定义为:任意一个点至多属于一个简单环$
$Q\le 10^5询问,(u, v)有多少条简单路径可达$

分析:

$考虑仙人掌的形态,任意2点之间的路径必然是由许多链和环构成$
$一个环有2种走法,每经过一个环方法数\times 2$
$那么问题转化为任意两点之间有多少简单环$
$那么显然边双缩点,点权为0/1(如果bcc大小>1)$
$之后LCA求2点之间的路径长度就好,记得特判LCA$
$答案ans=2^{环的个数}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//
// Created by TaoSama on 2016-08-07
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
vector<int> G[N], T[N];
int dfn[N], low[N], sz[N], id[N], bcc, dfsNum;
int stk[N], top;
void tarjan(int u, int f) {
dfn[u] = low[u] = ++dfsNum;
stk[++top] = u;
for(int v : G[u]) {
if(v == f) continue;
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++bcc;
while(true) {
int v = stk[top--];
++sz[bcc];
id[v] = bcc;
if(v == u) break;
}
}
}
const int LOG = 17;
int dep[N], dis[N], p[LOG][N];
void dfs(int u, int f) {
p[0][u] = f;
dis[u] = dis[f] + (sz[u] > 1);
for(int i = 1; i < LOG; ++i) p[i][u] = p[i - 1][p[i - 1][u]];
for(int v : T[u]) {
if(v == f) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
int lca(int u, int v) {
if(dep[u] > dep[v]) swap(u, v);
for(int i = 0; i < LOG; ++i)
if(dep[v] - dep[u] >> i & 1) v = p[i][v];
if(u == v) return u;
for(int i = LOG - 1; ~i; --i)
if(p[i][u] != p[i][v])
u = p[i][u], v = p[i][v];
return p[0][u];
}
int get(int u, int v) {
int g = lca(u, v);
return dis[u] + dis[v] - 2 * dis[g] + (sz[g] > 1);
}
void init() {
bcc = dfsNum = 0;
memset(dfn, 0, sizeof dfn);
tarjan(1, -1);
}
int ksm(int x, int n) {
int ret = 1;
for(; n; n >>= 1) {
if(n & 1) ret = 1LL * ret * x % MOD;
x = 1LL * x * x % MOD;
}
return ret;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
init();
for(int i = 1; i <= n; ++i) {
int u = id[i];
for(int j : G[i]) {
int v = id[j];
if(u == v) continue;
T[u].push_back(v);
}
}
dfs(1, 0);
int q; scanf("%d", &q);
while(q--) {
int x, y; scanf("%d%d", &x, &y);
int d = get(id[x], id[y]);
int ans = ksm(2, d);
printf("%d\n", ans);
}
return 0;
}

1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到