旅行 有向图两点可达性

(5 mins to read)

题意

给出一张随机生成的有向图,多次询问x点能否到达y点$n \leq 10^5,m \leq n + 5000,q \leq 3\times 10^5$

做法

跑一遍tarjan缩点成DAG设置根号个标记点,然后暴力跑出这些标记点能够到达的点,用bitset记录对于每个询问从x暴力dfs,遇到标记点则返回标记点选择度数最大的根号个复杂度:O(能过)

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
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
const int N = 1e5 + 5, M = 405;
vector<int> G[N], DAG[N];
vector<pii> edges;
int n, m, _;
int dfn[N], num[N], low[N], id, tot, sta[N], top, deg[N], idx[N];
bool in[N];
int vis[N], spe[N];
bitset<N> bit[M];
void tarjan(int u)
{
in[u] = 1;
low[u] = dfn[u] = ++id;
sta[++top] = u;
for(int v : G[u])
{
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(in[v]) low[u] = min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
tot++;
while(top)
{
int tmp = sta[top--];
in[tmp] = 0;
num[tmp] = tot;
if(tmp==u) break;
}
}
}
void dfs(int u, int t)
{
if(spe[u]) { bit[t] |= bit[spe[u]]; return; }
vis[u] = t;
bit[t].set(u);
for(int v : DAG[u])
{
if(vis[v]==t) continue;
dfs(v, t);
}
}
void prework()
{
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i);
for(auto it : edges)
{
int u = num[it.fi], v = num[it.se];
if(u!=v) DAG[u].pb(v), deg[u]++, deg[v]++;
}
int lim = (int)sqrt(tot) + 1;
iota(idx+1, idx+tot+1, 1);
sort(idx+1, idx+tot+1, [](int x, int y) {
return deg[x] > deg[y];
});
for(int i=1; i<=lim; i++)
{
dfs(idx[i], i);
spe[idx[i]] = i;
}
}
bool dfs2(int s, int t, int tt)
{
if(s==t) return 1;
if(spe[s]) return bit[spe[s]].test(t);
vis[s] = tt;
for(int ss : DAG[s])
{
if(vis[ss]==tt) continue;
if(dfs2(ss, t, tt)) return 1;
}
return 0;
}
void solve(int t)
{
int u, v;
scanf("%d%d", &u, &v);
++u, ++v;
if(num[u]==num[v]) puts("Good");
else puts((dfs2(num[u], num[v], t) ? "Good" : "Bad"));
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
++u, ++v;
G[u].pb(v);
edges.emplace_back(u, v);
}
prework();
scanf("%d", &_);
for(int i=1; i<=_; i++) solve(400+i);
return 0;
}