今天我刷题了吗
搜索文档…
离线 Tarjan 算法
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(5e5 + 10);
7
const int maxm(1e6 + 10);
8
int ecnt, qcnt;
9
bool vis[maxn];
10
int ehead[maxn], qhead[maxm];
11
int pre[maxn], ans[maxm];
12
13
struct edge {
14
int to, nxt;
15
} edges[maxm];
16
17
struct que {
18
int id, to, nxt;
19
} ques[maxm];
20
21
template<typename T = int>
22
inline const T read()
23
{
24
T x = 0, f = 1;
25
char ch = getchar();
26
while (ch < '0' || ch > '9') {
27
if (ch == '-') f = -1;
28
ch = getchar();
29
}
30
while (ch >= '0' && ch <= '9') {
31
x = (x << 3) + (x << 1) + ch - '0';
32
ch = getchar();
33
}
34
return x * f;
35
}
36
37
template<typename T>
38
inline void write(T x, bool ln)
39
{
40
if (x < 0) {
41
putchar('-');
42
x = -x;
43
}
44
if (x > 9) write(x / 10, false);
45
putchar(x % 10 + '0');
46
if (ln) putchar(10);
47
}
48
49
void addEdge(int u, int v)
50
{
51
edges[ecnt].to = v;
52
edges[ecnt].nxt = ehead[u];
53
ehead[u] = ecnt++;
54
}
55
56
void addQue(int id, int u, int v)
57
{
58
ques[qcnt].id = id;
59
ques[qcnt].to = v;
60
ques[qcnt].nxt = qhead[u];
61
qhead[u] = qcnt++;
62
}
63
64
int Find(int x)
65
{
66
return pre[x] == x ? x : pre[x] = Find(pre[x]);
67
}
68
69
void Union(int u, int v)
70
{
71
pre[Find(v)] = Find(u);
72
}
73
74
void dfs(int cur, int pre)
75
{
76
vis[cur] = true;
77
for (int i = ehead[cur]; compl i; i = edges[i].nxt) {
78
int nxt = edges[i].to;
79
if (nxt not_eq pre) {
80
dfs(nxt, cur);
81
}
82
}
83
for (int i = qhead[cur]; compl i; i = ques[i].nxt) {
84
int id = ques[i].id, nxt = ques[i].to;
85
if (vis[nxt]) {
86
ans[id] = Find(nxt);
87
}
88
}
89
Union(pre, cur);
90
}
91
92
void tarjan(int tot, int root)
93
{
94
for (int i = 1; i <= tot; ++i) {
95
pre[i] = i;
96
}
97
dfs(root, 0);
98
}
99
100
int main()
101
{
102
#ifdef ONLINE_JUDGE
103
#else
104
freopen("input.txt", "r", stdin);
105
#endif
106
ios::sync_with_stdio(false);
107
memset(ehead, -1, sizeof ehead);
108
memset(qhead, -1, sizeof qhead);
109
int n = read(), m = read(), s = read();
110
for (int i = 0; i < n - 1; ++i) {
111
int u = read(), v = read();
112
addEdge(u, v);
113
addEdge(v, u);
114
}
115
for (int i = 0; i < m; ++i) {
116
int u = read(), v = read();
117
addQue(i, u, v);
118
addQue(i, v, u);
119
}
120
tarjan(n, s);
121
for (int i = 0; i < m; ++i) {
122
write(ans[i], true);
123
}
124
return 0;
125
}
Copied!
最近更新 1yr ago
复制链接