图算法和图模型(一)

本篇内容主要写了和dfs有关的算法
比如tarjan算法, kosaraju算法等等
主要围绕图的割顶与桥展开

tarjan算法(无向图)

tarjan01
tarjan02
tarjan03
tarjan04

判桥

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
const int maxn = 100000 + 10;

// == define Edge and Graph ==
class Edge {
public:
int from, to;
Edge(int f = 0, int t = 0) : from(f), to(t) {}
};

vector<Edge> edges;
vector<int> G[maxn];
int n, m;
// == Edge and Graph finished ==

// == info for tarjan ==
int dfn[maxn], low[maxn];
bool bridge[maxn];
int Clock = 0;

void init() {
edges.clear();
edges.push_back(Edge());
edges.push_back(Edge());
// just for NIL

Set(dfn, 0);
Set(low, 0);
Set(bridge, 0);

Clock = 0;
}
// == info finished ==

// == tarjan ==
void addEdge(int u, int v) {
edges.push_back(Edge(u, v));
G[u].push_back(edges.size() - 1);
}

void tarjan(int u, int eID) {
dfn[u] = low[u] = ++Clock;
_for(i, 0, G[u].size()) {
int id = G[u][i];
int v = edges[id].to;

if(!dfn[v]) {
tarjan(v, id);
low[u] = min(low[u], low[v]);

if(low[v] > dfn[u]) bridge[id] = bridge[id^1] = 1;
}
else if(id != (eID^1)) {
low[u] = min(low[u], dfn[v]);
}
}
}
// == tarjan fisihed ==

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;
init();

_rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v), addEdge(v, u);
}
_rep(i, 1, n) if(!dfn[i]) tarjan(i, 0);
for(int i = 2; i < edges.size(); i += 2) {
if(bridge[i]) printf("%d %d\n", edges[i^1].to, edges[i].to);
}
}

判割点

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
const int maxn = 100000 + 10;

// == Edge and Graph definition ==
class Edge {
public:
int to;
Edge() {};
Edge(int to) : to(to) {}
};

vector<Edge> edges;
vector<int> G[maxn];
int n, m;
// == Edge and Graph finsihed ==

// == info used for tarjan ==
int dfn[maxn], low[maxn];
bool cut[maxn];
int Clock = 0;
int root = 0;

void init() {
Clock = 0;
root = 0;
edges.clear();
edges.push_back(Edge());
edges.push_back(Edge());
// NIL edges

Set(dfn, 0);
Set(low, 0);
Set(cut, 0);
}
// == info finished ==

// == tarjan ==
void addEdge(int u, int v) {
edges.push_back(Edge(v));
G[u].push_back(edges.size() - 1);
}

void tarjan(int u) {
dfn[u] = low[u] = ++Clock;
int cld = 0;

_for(i, 0, G[u].size()) {
int v = edges[G[u][i]].to;

if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) {
cld++;
if(u != root || cld > 1) cut[u] = true;
}
}
else low[u] = min(low[u], dfn[v]);
}
}
// == tarjan finsihed ==

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;
init();

_rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v), addEdge(v, u);
}

_rep(i, 1, n) if(!dfn[i]) {
root = i;
tarjan(i);
}

_rep(i, 1, n) if(cut[i]) printf("%d ", i);
puts("are cut-vertexes");
}

BZOJ1123

tarjan05

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
const int maxn = 100000 + 10;

class Edge {
public:
int from, to;
Edge(int f = 0, int t = 0) : from(f), to(t) {}
};

vector<Edge> edges;
vector<int> G[maxn];
int dfn[maxn], low[maxn], cut[maxn], size[maxn];
llong ans[maxn];
int clk;
int root;

int n, m;

void init() {
edges.clear();
edges.push_back(Edge());

Set(dfn, 0);
Set(low, 0);
Set(ans, 0);
Set(cut, 0);
Set(size, 0);

clk = 0;
}

void addEdge(int u, int v) {
edges.push_back(Edge(u, v));
G[u].push_back(edges.size() - 1);
}

void tarjan(int u) {
dfn[u] = low[u] = ++clk;
size[u] = 1;

int cld = 0, sum = 0;

_for(i, 0, G[u].size()) {
int eid = G[u][i];
int v = edges[eid].to;
//debug(v);

if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
size[u] += size[v];

if(low[v] >= dfn[u]) {
cld++;
ans[u] += (llong)(size[v]) * (n - size[v]);
sum += size[v];

if(u != root || cld > 1) cut[u] = 1;
}
}
else low[u] = min(low[u], dfn[v]);
}
if(!cut[u]) ans[u] = 2 * (n - 1);
else {
ans[u] += ((n - 1) + (llong)(n - 1 - sum) * (sum + 1));
}
}

int main() {
freopen("input.txt", "r", stdin);
init();

scanf("%d%d", &n, &m);

_for(i, 0, m) {
int u, v;
scanf("%d%d", &u, &v);
if(u == v) continue;

addEdge(u, v);
addEdge(v, u);
}
// node start from 1

root = 1;
tarjan(root);

_rep(i, 1, n) printf("%lld\n", ans[i]);
}

tarjan无向图的双连通分量

tarjan06
tarjan07
tarjan08
tarjan09

tarjan算法求边双连通分量并缩点

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
134
const int maxn = 100000 + 10;

// == define Edge and Graph ==
class Edge {
public:
int to;
Edge() {}
Edge(int to) : to(to) {}
};

vector<Edge> edges;
vector<int> G[maxn];
// == Edge and Graph finished ==

// == eDCC graph ==
vector<Edge> eDCC;
vector<int> GC[maxn];
// == eDCC finsihed ==

// == tarjan info ==
int n, m;
int dfn[maxn], low[maxn];
bool bridge[maxn << 1];
int Clock = 0;

void init() {
Clock = 0;
edges.clear();
edges.push_back(Edge());
edges.push_back(Edge());
// NIL edges

Set(dfn, 0);
Set(low, 0);
Set(bridge, 0);
}
// == tarjan info finsihed ==

// == tarjan ==
void addEdge(int u, int v) {
edges.push_back(Edge(v));
G[u].push_back(edges.size() - 1);
}

void tarjan(int u, int in_edge) {
dfn[u] = low[u] = ++Clock;
_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[eid].to;

if(!dfn[v]) {
tarjan(v, eid);
low[u] = min(low[u], low[v]);

if(low[v] > dfn[u]) bridge[eid] = bridge[eid^1] = 1;
}
else if(eid != (in_edge^1)) {
low[u] = min(low[u], dfn[v]);
}
}
}
// == tarjan finsihed ==

// == calculate eDCC ==
int dcc = 0;
int belong[maxn];
void initDCC() {
eDCC.clear();
eDCC.push_back(Edge());
eDCC.push_back(Edge());
// used as NIL

dcc = 0;
Set(belong, 0);
}

void add_c(int u, int v) {
eDCC.push_back(Edge(v));
GC[u].push_back(eDCC.size() - 1);
}

void dfs(int u) {
belong[u] = dcc;
_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[eid].to;
if(belong[v] || bridge[eid]) continue;
dfs(v);
}
}

void getDCC() {
_rep(i, 1, n) {
if(!belong[i]) {
++dcc;
dfs(i);
}
}
printf("There are %d e-DCCs.\n", dcc);
_rep(i, 1, n) printf("%d belongs to DCC %d.\n", i, belong[i]);

_for(i, 2, edges.size()) {
int u = edges[i^1].to, v = edges[i].to;
if(belong[u] == belong[v]) continue;
add_c(belong[u], belong[v]);
}

printf("缩点之后的森林,点数 %d,边数 %d\n", dcc, (eDCC.size()-1)>>1);
for(int i = 2; i < eDCC.size(); i += 2) {
printf("eDCC%d <---> eDCC%d\n", eDCC[i^1].to, eDCC[i].to);
}
}
// == eDCC finsihed ==

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;

init();
_rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}

// == tarjan ==
_rep(i, 1, n) if(!dfn[i]) tarjan(i, 0);
for(int i = 2; i < edges.size(); i += 2) if(bridge[i]) {
printf("%d %d\n", edges[i^1].to, edges[i].to);
}

// == eDCC ==
initDCC();
getDCC();
}

tarjan算法求点双连通分量并缩点

连通分量的编号统一用 $cnt$ 表示

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
const int maxn = 100000 + 10;

// == define Edge and Graph ==
class Edge {
public:
int to;
Edge() {}
Edge(int to) : to(to) {}
};

vector<Edge> edges;
vector<int> G[maxn];
// == Edge and Graph finsihed ==

// == tarjan info ==
int n, m;
vector<int> dcc[maxn];
int dfn[maxn], low[maxn], cnt = 0, Clock = 0;
bool cut[maxn];

stack<int> stk;
int root = 0;

void init() {
cnt = 0;
Clock = 0;
root = 0;

edges.clear();
edges.push_back(Edge());
edges.push_back(Edge());
// NIL edges

Set(dfn, 0);
Set(low, 0);
Set(cut, 0);

while(!stk.empty()) stk.pop();
}
// == tarjan info finished ==

// == tarjan main ==
void addEdge(int u, int v) {
edges.push_back(Edge(v));
G[u].push_back(edges.size() - 1);
}

void tarjan(int u) {
dfn[u] = low[u] = ++Clock;
stk.push(u);

if(u == root && G[u].size() == 0) {
// single point
dcc[++cnt].push_back(u);
return;
}

int cld = 0;
_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[eid].to;

if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);

// judge cut-point
if(low[v] >= dfn[u]) {
cld++;
if(u != root || cld > 1) cut[u] = true;

// save the point in the same DCC
cnt++;
for(;;) {
int z = stk.top(); stk.pop();
dcc[cnt].push_back(z);
if(z == v) break;
}
dcc[cnt].push_back(u);
}
}
else low[u] = min(low[u], dfn[v]);
}
}
// == tarjan finsihed ==

// == vDCC Graph ==
vector<int> GC[maxn];
vector<Edge> vDCC;
int belong[maxn], newID[maxn];
int num = 0;

void initDCC() {
vDCC.clear();
vDCC.push_back(Edge());
vDCC.push_back(Edge());
// NIL edges

Set(belong, 0);
Set(newID, 0);
num = 0;
}

void add_c(int u, int v) {
vDCC.push_back(Edge(v));
GC[u].push_back(vDCC.size() - 1);
}

// == vDCC finsihed ==

void getDCC() {
// input DCC nodes and data
_rep(i, 1, cnt) {
printf("v-DCC #%d:", i);
_for(j, 0, dcc[i].size()) {
printf(" %d", dcc[i][j]);
}
puts("");
}

// point reduction
num = cnt;
_rep(i, 1, n) if(cut[i]) newID[i] = ++num;

// build new Graph for vDCC
_rep(i, 1, cnt) _for(j, 0, dcc[i].size()) {
int z = dcc[i][j];
if(cut[z]) {
add_c(i, newID[z]), add_c(newID[z], i);
}
else belong[z] = i;
}

// print info
printf("缩点之后的森林,点数 %d, 边数 %d\n", num, (int)(vDCC.size() - 1) >> 1);
printf("下图编号 1~%d 的为原图的v-DCC,编号 >=%d 的为原图的割点\n", cnt, cnt);
for(int i = 2; i < vDCC.size(); i += 2) {
printf("vDCC#%d <-----> vDCC#%d\n", vDCC[i^1].to, vDCC[i].to);
}
}
// == vDCC Graph finished ==

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;

init();
_rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
if(u == v) continue;
addEdge(u, v), addEdge(v, u);
}

// == tarjan ==
_rep(i, 1, n) if(!dfn[i]) {
root = i, tarjan(i);
}
_rep(i, 1, n) if(cut[i]) printf("%d ", i);
puts("are cut vertexes");
// == tarjan finished ==

initDCC();
getDCC();
}

euler路径

euler

POJ2230

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
const int maxn = 100000 + 10;
int n, m;
int st;
vector<int> G[maxn];
int head[maxn];
stack<int> stk;
vector<int> ans;

struct Edge {
int u, v;
Edge(int u = 0, int v = 0) : u(u), v(v) {}
};

vector<Edge> edges;

void init() {
_for(i, 0, maxn) G[i].clear();
while(!stk.empty()) stk.pop();
edges.push_back(Edge());
edges.push_back(Edge());
Set(head, 0);
ans.clear();
}

void addEdge(int u, int v) {
edges.push_back(Edge(u, v));
G[u].push_back(edges.size() - 1);
}

void euler() {
stk.push(st);
while (!stk.empty()) {
int x = stk.top(), i = head[x];
// debug(x);

if(i < G[x].size()) {
int eid = G[x][i];
int y = edges[eid].v;

stk.push(y);
head[x] = i + 1;
}
else {
stk.pop();
ans.push_back(x);
}
}
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;

_rep(i, 1, m) {
int x, y;
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}

st = 1;
euler();
for(int i = ans.size() - 1; i >= 0; i--) printf("%d\n", ans[i]);
}

tarjan算法(有向图)

tarjan10

tarjan有向图的强连通分量

tarjan11
tarjan12
tarjan13

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
134
const int maxn = 100000 + 10;

// == define Edge and Graph ==
class Edge {
public:
int to;
Edge() {}
Edge(int to) : to(to) {}
};

vector<Edge> edges;
vector<int> G[maxn];

inline void addEdge(int u, int v) {
edges.push_back(Edge(v));
G[u].push_back(edges.size() - 1);
}
// == Edge and Graph finsihed ==

// == SCC Graph ==
vector<int> GC[maxn];
vector<int> SCC[maxn];
vector<Edge> eSCC;

inline void add_c(int u, int v) {
eSCC.push_back(Edge(v));
GC[u].push_back(eSCC.size() - 1);
}
// == SCC finished ==

// == tarjan info ==
int dfn[maxn], low[maxn];
int ins[maxn];
int cnt = 0, Clock = 0;
int belong[maxn];
stack<int> stk;

void init() {
Set(dfn, 0);
Set(low, 0);
cnt = Clock = 0;

edges.push_back(Edge());
edges.push_back(Edge());
// used as NIL
}

void initSCC() {
Set(belong, 0);
Set(ins, 0);

eSCC.push_back(Edge());
eSCC.push_back(Edge());
// used as NIL

while (!stk.empty()) stk.pop();
}
// == tarjan info finished ==

// == tarjan and get SCC ==
void tarjan(int u) {
dfn[u] = low[u] = ++Clock;
stk.push(u), ins[u] = 1;

_for(i, 0, G[u].size()) {
int v = edges[G[u][i]].to;
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(ins[v]) {
low[u] = min(low[u], dfn[v]);
}
}

if(low[u] == dfn[u]) {
cnt++;
for(;;) {
int z = stk.top(); stk.pop(); ins[z] = 0;
belong[z] = cnt;
SCC[cnt].push_back(z);

if(z == u) break;
}
}
}
// == tarjan and SCC finsihed ==

int n, m;
int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;

init();
initSCC();

_rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
}

_rep(i, 1, n) if(!dfn[i]) tarjan(i);

_rep(u, 1, n) _for(i, 0, G[u].size()) {
int v = edges[G[u][i]].to;
if(belong[v] == belong[u]) continue;

add_c(belong[u], belong[v]);
}

// print ans
_rep(i, 1, cnt) {
printf("连通分量#%d含有的点为:", i);
_for(j, 0, SCC[i].size()) printf(" %d", SCC[i][j]);
printf("\n");
}
puts("");

printf("缩点之后的图显示如下: \n");
_rep(i, 1, cnt + 1) {
if(GC[i].size() == 0) continue;

_for(j, 0, GC[i].size()) {
int v = eSCC[GC[i][j]].to;
printf("#%d <==> #%d\n", i, v);
}
}

_rep(i, 1, n) {
printf("low[%d]=%d ",i, low[i]);
}
puts("");
}

树的直径

BZOJ1912.jpg
BZOJ1912.jpg

树形dp求树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 树形dp求树的直径
void dp(int u, int& ans) {
vis[u] = 1;
_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[G[u][i]].to;
if(vis[v]) continue;

dp(v, ans);
ans = max(ans, d[u] + d[v] + edges[eid].w);
d[u] = max(d[u], d[v] + edges[eid].w);
}
}

int main() {
ans = 0;
memset(d, 0, sizeof(d));
memset(vis, 0, sizeof(vis));

// root一般取直径的一个端点
dp(root, ans);
}

两次dfs求树的直径并记忆化

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
int pa[maxn], d[maxn], vis[maxn];
void dfs(int u, int& p) {
vis[u] = 1;

_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[eid].to;
if(vis[v]) continue;

if((d[v] = d[u] + edges[eid].w) >= d[p]) p = v;
pa[v] = eid;

dfs(v, p);
}

vis[u] = 0;
}
// 这时候获取了直径的一个端点p
// we get one endpoint of diameter

int main() {
Set(pa, 0);
Set(d, 0);
Set(vis, 0);

// first dfs to find p and get d[]
int p = 1;
dfs(1, p);

// second dfs
d[p] = pa[p] = 0;
int q = p;
dfs(p, q);

// p-->q is the path of diameter
}

实践

BZOJ1912

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
const int maxn = 100000 + 10;

class Edge {
public:
int to, weight;
Edge(int t = 0, int w = 0) : to(t), weight(w) {}
};

vector<Edge> edges;
vector<int> G[maxn];
int n, k;
int pa[maxn * 2], d[maxn * 2], vis[maxn * 2];

void init() {
edges.push_back(Edge());
edges.push_back(Edge());

_for(i, 0, maxn) G[i].clear();
Set(pa, 0);
Set(d, 0);
Set(vis, 0);
}

void addEdge(int from, int to, int w) {
edges.push_back(Edge(to, w));
G[from].push_back(edges.size() - 1);
}

void dfs(int u, int& to) {
vis[u] = 1;

_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[eid].to;

if(vis[v]) continue;
if((d[v] = d[u] + edges[eid].weight) >= d[to]) to = v;
pa[v] = eid;

dfs(v, to);
}

vis[u] = 0;
}

void dp(int u, int& ans) {
vis[u] = 1;
_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[eid].to;

if(vis[v]) continue;
dp(v, ans);

ans = max(ans, d[u] + d[v] + edges[eid].weight);
d[u] = max(d[u], d[v] + edges[eid].weight);
}
}

int main() {
freopen("input.txt", "r", stdin);

init();
scanf("%d%d", &n, &k);
_for(i, 0, n) {
int u, v;
scanf("%d%d", &u, &v);

addEdge(u, v, 1);
addEdge(v, u, 1);
}

// then solve the problem
int to = 1;
dfs(1, to);

d[to] = pa[to] = 0;
int tto = to;
dfs(to, tto);
// [to, tto] is the longest path in a tree

int ans = ((n - 1) << 1) - d[tto] + 1;

if(k == 2) {
while (pa[tto]) {
int eid = pa[tto];
edges[eid].weight = edges[eid ^ 1].weight = -1;
tto = edges[eid ^ 1].to;
}

tto = 0;
Set(d, 0);
Set(vis, 0);
dp(to, tto);
ans -= (tto - 1);
}

printf("%d\n", ans);
}

tarjan算法实践