学习笔记_ tarjan算法家族 [tarjan, 图论, 割点, 学习笔记]

趁着学割点把(我知道的)tarjan搞一遍吧…

引言

求割点/边那可是宽嫂从初二(真 中二)就有的梦想…
那时候宽嫂在实验中学, 和那里的小伙伴一起去郑州懵逼, 虽然成天被鈡神吊打(和怒怼)…但是想想还是挺怀念的呢…
那时候去郑州…什么都不会…BFS打错, 多重背包都不会, 暴力没时间写, 晚上睡不好上课真的睡着了, 考试场场爆零…
听树边和返祖边横叉边倒是似乎挺明白的…难道对图论比较敏感讲的太简单?

Tarjans

Tarjan强连通分量

tarjan是在有向图中求强连通分量(一个点集, 中间的点可以两两互相到达), 的一种算法, 复杂度为$O(n + m)$

具体实现是记录一个栈表示当前搜索到可能是强连通分量的点, 当前节点经过一条非树边能达到的最高祖先(low[]), 当前节点的时间戳(dfn[]), 在dfs每一个节点的时候更新他的low(初始化low[dq] = dfn[dq], 如果在遍历完当前节点的子树后当前节点的low == dfn那么说明栈中的节点组成了一个强连通分量(不能再到达自己的祖先了), 还是挺妙的对吧? 需要仔细意会一下…

强连通分量有一些很好的性质, 比如说图上DP中, 一个强连通分量总是可以互相转移的, 这样我们就可以将许多一般的图转化为DAG从而在新图上做DP

Tarjan求割点

我们只需要在上面的tarjan上改一下就吼啦…
割点, 意味着子孙节点不能到达自己的祖先,
如果一个点子孙的low都比自己的dfn大, 也就是说子孙能到达的最高的节点不会比自己高, 只能在自己以下的地方转悠, 这个点就是一个割点
而且因为在无向图中没有横叉边(在有向图中一条使一个点只能通进一个连通分量却不能从那个连通分量到自己所属的连通分量的边)(无向图通进去肯定能出来啊), 所以我们连那个栈都不用写…
注意每次dfs的根节点要特判是否是割点: 有没有互不联通的两棵(及以上的子树)

似乎统计割点的时候最好是打标记, 最后一起遍历, 好像直接在dfs遍历的时候会有重复的统计

割点在图论的路径上面有一些应用, 比如必经点啥的…

Tarjan求割边

割边, 就是边的一段和另一端没有其他路径相连, 那么我们也可以通过tarjan来求这个割边, 一条边的to节点不能到达比from更靠上的节点(low[to] > dfn[from]), 那么这条边就是一条割边

可以求个必经边啥的…

Tarjan求LCA

好像没啥用…
离线(当年这是我第一次接触离线), 就是用链式前向星把和每一个节点有关系的询问挂在节点上, 然后dfs退出一个节点时就把他代表的并查集和父节点合并起来, 并标记这个节点为已经访问, 遍历与这个节点相关的询问, 如果另一个节点也被标记为了访问, 那么这个询问的答案就是find(dq)
其实就是相当于自下而上把这棵树构造了出来, 如果在某个时刻询问的两个点都恰好已经被构造了, 那么这两个点的LCA就是当前这棵没构造完的树的根, 是不是很妙?

完了

沙茶的 代码

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
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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#define MAXN (10000 + 5)
#define MAXM (100000 + 5)
using namespace std;
struct edg
{
int from;
int to;
int next;
};
struct suodian
{
int n;
int m;
int low[MAXN];
int dfn[MAXN];
int cntd;
bool instack[MAXN];
stack<int> s;

edg b[MAXM];
int g[MAXN];
int cntb;

int fa[MAXN];
int nn, mn;
edg bn[MAXN];
int gn[MAXN];
int cntbn;

int w[MAXN];
int wn[MAXN];
int dans[MAXN];
int ans;

void init()
{
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(instack, false, sizeof(instack));
memset(g, 0, sizeof(g));
memset(wn, 0, sizeof(wn));
memset(dans, 0, sizeof(dans));
nn = 0;
mn = 0;
cntb = cntd = cntbn = ans = 0;

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
}
int srx, sry;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
adn(b, g, &cntb, srx, sry);
}
}

void adn(edg* bx, int* gx, int* cntx, int from, int to)
{
bx[++(*cntx)].next = gx[from];
bx[(*cntx)].from = from;
bx[(*cntx)].to = to;
gx[from] = (*cntx);
}

void tarjan(int dq)
{
low[dq] = dfn[dq] = ++cntd;
instack[dq] = true;
s.push(dq);
for (int i = g[dq]; i; i = b[i].next)
{
if (!dfn[b[i].to])
{
tarjan(b[i].to);
low[dq] = min(low[dq], low[b[i].to]);
}
else if (instack[b[i].to])
{
low[dq] = min(low[dq], dfn[b[i].to]);
}
}
if (low[dq] == dfn[dq])
{
while(!s.empty() && s.top() != dq)
{
fa[s.top()] = dq;
instack[s.top()] = false;
s.pop();
}
if (!s.empty())
{
fa[dq] = dq;
instack[dq] = false;
s.pop();
}
nn++;
}
}

void inite()
{
for (int i = 1; i <= n; i++)
{
wn[fa[i]] += w[i];
}
for (int i = 1; i <= m; i++)
{
if (fa[b[i].from] != fa[b[i].to])
{
adn(bn, gn, &cntd, fa[b[i].from], fa[b[i].to]);
}
}
}

void dp(int startDash)
{
queue<int> q;
q.push(startDash);
dans[startDash] = wn[startDash];
bool inq[MAXN];
memset(inq, false, sizeof(inq));
while(!q.empty())
{
int dq = q.front();
q.pop();
inq[dq] = false;
ans = max(ans, dans[dq]);
for (int i = gn[dq]; i; i = bn[i].next)
{
if (dans[bn[i].to] < dans[dq] + wn[bn[i].to])
{
dans[bn[i].to] = dans[dq] + wn[bn[i].to];
if (!inq[bn[i].to])
{
q.push(bn[i].to);
}
}
}
}
}
}mhr;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
mhr.init();
for (int i = 1; i <= mhr.n; i++)
{
if (!mhr.dfn[i])
{
mhr.tarjan(i);
}
}
mhr.inite();
for (int i = 1; i <= mhr.n; i++)
{
if (!mhr.dans[mhr.fa[i]])
{
mhr.dp(mhr.fa[i]);
}
}
printf("%d", mhr.ans);
return 0;
}

/*
2 2
1 1
1 2
2 1
*/

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
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>
#define MAXN (100000 + 5)
#define MAXM (100000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define pii pair<int, int>
using namespace std;
struct edg
{
int from, to, next;
} b[MAXM << 1];
int g[MAXN], cntb;
bool ans[MAXN];
int dfn[MAXN], low[MAXN], cntdfn, n, m;
int bh[MAXN << 1];
map<int, int> tz;
void init();
void tarjan(int, int);
inline void adn(int, int);
bool cmp(int x, int y)
{
return x < y;
}
bool comp(pii x, pii y)
{
return x < y;
}
int main()
{
// freopen("in.in", "r", stdin);
// freopen("wa.out", "w", stdout);
init();
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
tarjan(i, i);
}
int outans = 0;
for (int i = 1; i <= n; i++)
if (ans[i])
++outans;
printf("%d\n", outans);
for (int i = 1; i <= n; i++)
if (ans[i])
printf("%d ", bh[i]);
return 0;
}
void init()
{
memset(ans, false, sizeof(ans));
scanf("%d%d", &n, &m);
pii node[MAXM];
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &node[i].first, &node[i].second);
if (node[i].first < node[i].second)
swap(node[i].first, node[i].second);
bh[i] = node[i].first, bh[i + m] = node[i].second;
}
sort(bh + 1, bh + (m << 1) + 1, cmp);
unique(bh + 1, bh + (m << 1) + 1);
sort(bh + 1, bh + n + 1, cmp);
for (int i = 1; i <= n; i++)
tz[bh[i]] = i;
sort(node + 1, node + m + 1, comp);
m = unique(node + 1, node + m + 1) - node - 1;
for (int i = 1; i <= m; i++)
adn(tz[node[i].first], tz[node[i].second]), adn(tz[node[i].second], tz[node[i].first]);
}
inline void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from, b[cntb].to = to;
g[from] = cntb;
}
void tarjan(int dq, int fa)
{
low[dq] = dfn[dq] = ++cntdfn;
int child = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if (!dfn[b[i].to])
{
++child;
tarjan(b[i].to, dq);
low[dq] = min(low[dq], low[b[i].to]);
if (low[b[i].to] >= dfn[dq] && dq != fa)
ans[dq] = true;
}
else
low[dq] = min(low[dq], dfn[b[i].to]); // 无向图 DFS 树没有横叉边, 所有非树边均为返祖边
}
if (dq == fa)
{
if (child > 1)
ans[dq] = true;
}
}

/*
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
*/

Tarjan求割边

未完待续(+1s)…

Tarjan求LCA

未完待续(+1s)…

呐, 他们说 怀旧是因为现在过得不好哦~

By 突然有点怀旧的 Cansult