算法学习笔记(17): tarjan算法
tarjan算法在众多问题都有解决方法。
新概念定义
建立在一个有向图的DFS生成树中：
graph TD
1((1))
2((2))
3((3))
4((4))
5((5))
6((6))
7((7))
8((8))
9((9))
1 --> 2
2 --> 3
3 --> 4
3 --> 5
5 --> 6
3 -.-> 6
2 --> 7
7 -.-> 1
1 --> 8
8 --> 9
9 -.-> 7上图的搜索顺序为 1 2 3 4 5 6 7 8 9
在对于一个有向图进行DFS生成树的时候，我们使用visited来标记已经走过的节点，对于上图，实边就是我们生成树的部分，但是其中的虚线边也是我们dfs走到的，因为探到的点已经visited，所以这个边并不加入生成树。我们有以下分类：
- 树边：搜索中探到的点并没有被访问过，这条边也被加入生成树中。
- 返祖边：探到的点visited了，而且是父节点中的。（7 → 1）
- 横叉边：探到的点visited了，但不是父节点中的。（9 → 7）
- 前向边：探到的点visited了，在搜索的时候子树中的结点（3 → 6）
强联通分量
targan基于对图的DFS生成树，运用了两个特殊的数组，或者是两个特殊的属性值：dfn时间戳和low追溯值。
- dfn时间戳：dfn[x]=节点x被第一次访问时的顺序
- low追溯值：low[x]=从节点x出发，能访问到的最早的时间戳
算法步骤：
- DFS过程中，如果这个点没被访问，就dfs它，并根据它的low值更新low值。
- 如果被访问过，那么判断这个边的点是否在栈中，如果不在说明已经属于某个scc，在就根据它的dfn更新自己的low值
- 如果遇到dfn[cur] == low[cur]，则不断出栈直到自己，这段的点属于一个SCC。
void tarjan(const vector<int> *adj, int n){
vector<int> dfn(n + 1);
vector<int> low(n + 1);
int dfnNo = 1;
vector<bool> inStack(n + 1);
stack<int> stk;
vector<vector<int>> sccs; // 存储所有的强连通分量
function<void(int)> dfs = [&](int cur){
dfn[cur] = low[cur] = dfnNo;
dfnNo++;
stk.push(cur);
inStack[cur] = true;
for(int to: adj[cur]){
if(dfn[to] == 0){ // to 没有被访问到
dfs(to);
low[cur] = min(low[cur], low[to]);
}else if(inStack[to]){
low[cur] = min(low[cur], dfn[to]);
}
}
if (dfn[cur] == low[cur]) { // 如果当前节点是SCC的根节点
vector<int> scc;
int node;
do {
node = stk.top();
stk.pop();
inStack[node] = false;
scc.push_back(node);
} while (node != cur);
sccs.push_back(scc);
}
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) {
dfs(i);
}
}
};
} 算法理解：
DFS生成树的作用（dfn的作用）
如果是根据一颗生成树中的子树来说，这个子树的根节点一定是dfn在子树中最小的。还有一点是这个根节点可以访问到子树中的所有点。
如果一个节点A的dfn == low，说明它的子树中的节点并不会访问到它以上的点，如果访问到了，那么它的low值也会被更新得更低。
为什么能直接出栈到这个节点为止，因为 既然能到这个节点，说明这一段里面的所有点都dfn != low, 而他们有能到达的low点，不会低于A，如果高于A但是不等于自己，说明在之前就已经被出栈了。所以一旦有一段出栈，它们的low值都是一样的。
我们可以保证的是，每次出栈的一组是一个子树，所以的所有节点都可以从根节点遍历到，又low值的定义是可以访问到的最小dfn值，也就成了SCC。
关于Low值更新
需要弄清楚的事dfn标号的顺序和low值更新的顺序，low值是在dfs之后进行的，也就是回溯的时候才能处理完的值。由于是回溯，所以上面的点能访问到下面的点，也就可以根据下面的点来更新low值。
为什么有的时候用low值更新，有的时候用dfn更新，用low值更新是因为low是由子节点能访问到更小的点决定的被储存于low，如果访问到已经instack的点，那么这个点的编号肯定是最小的，所以根据这个点的dfn更新。
割点与割边（桥）
- 割点：删除了一个点后，联通块多了一块，这个点就是割点
- 割边：删除了一条边后，联通块多了一块，这个边就是割边
寻找割点
同样使用了tarjan算法，维护low和dfn两个属性。
low代表不经过其父亲能到达的最小的时间戳。
算法步骤：
- 开始 DFS，我们判断某个点是否是割点的根据是：
- 对于某个顶点u，如果存在至少一个顶点 v(u 的儿子），使得 low[v] ≥ dfn[u]，即不能回到祖先，那么 u点为割点。
- 特殊考虑起始点：如果起点在搜索树内有两个及以上的儿子，那么起点一定是割点
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dfn[100001], low[100001], inde, res;
bool vis[100001], flag[100001];
vector<int> edge[100001];
void Tarjan(int cur, int par)
{
vis[cur] = true; // 标记
low[cur] = dfn[cur] = ++inde; // 打上时间戳
int child = 0; // 生成树中的子节点数量
for (auto v : edge[cur]){
if (!vis[v])
{
child++;
Tarjan(v, cur);
low[cur] = min(low[cur], low[v]);
if (par != cur && low[v] >= dfn[cur] && !flag[cur])
{ // 记录cur
flag[cur] = true;
res++;
}
}
else if (v != par){
low[cur] = min(low[cur], dfn[v]);
}
}
// 根节点需要 2 个儿子才可以， 用par == cur判断根节点
if (par == cur && child >= 2 && !flag[cur])
{ // 记录cur
flag[cur] = true;
res++;
}
}算法思路和细节
low[v] ≥ dfn[u]为什么就是割点，此时是从父节点到了这个点，因为这里的low忽略了连接父节点的边，这句话说明了v不通过这条父节点的边就连接不到u，又因为u也有父节点，所以在没有u的情况下，v肯定无法连接到u的父节点，证明了u是割点。
为什么根节点考虑不一样？
就如前面说的，证明利用到了u的父节点，作为根节点并没有父节点，因此利用了最小生成树，从根节点出去的第一个子树A包含了所有从ROOT - A的点，因此其他没走过的点就必须要从ROOT的其他边通过，所以删掉ROOT，这些点就走不到了，ROOT因此成为割点。
寻找割边
实际上刚刚的点和寻找割边思路十分相似。
我们的之前的重点放在不能走到u的父节点上，使用low[v] >= dfn[cur]，实际上就是cur往下发出的这条边，此时改为low[v] > dfn[cur]，如果不能连接到cur，就代表一旦断掉cur往下的这条边，就会不连通，所以割点和割边的寻找方法类似。
int low[MAXN], dfn[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];
void tarjan(int u, int fa) {
father[u] = fa;
low[u] = dfn[u] = ++dfs_clock;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
isbridge[v] = true;
++cnt_bridge;
}
} else if (dfn[v] < dfn[u] && v != fa) {
low[u] = min(low[u], dfn[v]);
}
}
}双连通分量
我们解决了有向图中的强联通分量，如果把相似问题移到无向图上：
边双连通
我们定义边双连通：
在一张连通的无向图中，对于两个点 u 和 v，无论删去哪一条边（只能删去一条）都不能使它们不连通。
例如一个无向环中的每一个点，它们都是双联通的，去掉任意的一条，它们还是在一条链上联通，所以它们是边双连通。
解法一
删去所有的割边，剩下的每个连同块就是一个边连通分量。
用dfs遍历每个连通块记录即可。
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 5e5 + 5, M = 2e6 + 5;
int n, m, ans;
int tot = 1, hd[N];
struct edge
{
int to, nt;
} e[M << 1];
void add(int u, int v) { e[++tot].to = v, e[tot].nt = hd[u], hd[u] = tot; }
void uadd(int u, int v) { add(u, v), add(v, u); }
bool bz[M << 1];
int bcc_cnt, dfn[N], low[N], vis_bcc[N];
vector<vector<int>> bcc;
void tarjan(int x, int in)
{
dfn[x] = low[x] = ++bcc_cnt;
for (int i = hd[x]; i; i = e[i].nt)
{
int v = e[i].to;
if (dfn[v] == 0)
{
tarjan(v, i);
if (dfn[x] < low[v])
bz[i] = bz[i ^ 1] = 1;
low[x] = min(low[x], low[v]);
}
else if (i != (in ^ 1))
low[x] = min(low[x], dfn[v]);
}
}
void dfs(int x, int id)
{
vis_bcc[x] = id, bcc[id - 1].push_back(x);
for (int i = hd[x]; i; i = e[i].nt)
{
int v = e[i].to;
if (vis_bcc[v] || bz[i])
continue;
dfs(v, id);
}
}
int main()
{
scanf("%d%d", &n, &m);
int u, v;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &u, &v);
if (u == v)
continue;
uadd(u, v);
}
for (int i = 1; i <= n; i++)
if (dfn[i] == 0)
tarjan(i, 0);
for (int i = 1; i <= n; i++)
if (vis_bcc[i] == 0)
{
bcc.push_back(vector<int>());
dfs(i, ++ans);
}
printf("%d\\n", ans);
for (int i = 0; i < ans; i++)
{
printf("%llu", bcc[i].size());
for (int j = 0; j < bcc[i].size(); j++)
printf(" %d", bcc[i][j]);
printf("\\n");
}
return 0;
}解法二
寻找边双连通和强联通分量的相似之处，对于强联通分量，就是在寻找一个环，而边联通分量和环是一样的，在一个环内的所有点必定是边双连通的。
或者说，在 DFS 生成树上的一个强连通分量，在原无向图中是边双连通分量。
所以求边双连通分量的过程实际上就是求强连通分量的过程。
复杂度O(M + N)
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m;
vector<vector<int>> adj(N); // 邻接表表示图
vector<int> dfn(N), low(N), inStack(N);
int bcc_cnt = 0;
vector<vector<int>> bcc; // 存储双连通分量
stack<int> st;
void add_edge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // 无向图加两条边
}
void tarjan(int u, int parent) {
low[u] = dfn[u] = ++bcc_cnt;
st.push(u);
inStack[u] = 1;
int p = 0; // 让重边只判断一次
for (int v : adj[u]) {
if (v == parent and p == 0){
p++; // 让重边只判断一次
continue; // 忽略返回父节点的边
}
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) { // 找到一个双连通分量
vector<int> component;
component.push_back(u);
while(st.top() != u){
component.push_back(st.top());
inStack[st.top()] = 0;
st.pop();
}
st.pop();
bcc.push_back(component);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
if (u != v) add_edge(u, v); // 忽略自环
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) tarjan(i, 0);
}
cout << bcc.size() << "\\n";
for (const auto& component : bcc) {
cout << component.size();
for (int v : component) {
cout << " " << v ;
}
cout << "\\n";
}
return 0;
}点双连通
在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和v自己）都不能使它们不连通，我们就说 v 和 u 点双连通。
解法一
回忆找割点算法 ，通过找割点的判断方式找到割点，再和边双连通分量一样的原理，和寻找强联通类似，将点从栈中取出存入一个点双连通分量。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5; // 最大节点数
int n, m;
vector<int> adj[N]; // 邻接表表示图
vector<int> dfn(N), low(N), sta(N), bcc[N];
int timestamp = 0, bcc_count = 0, top = 0;
vector<bool> is_cut(N);
int root;
void add_edge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // 无向图，两条边
}
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
sta[++top] = u;
if (u == root && adj[u].empty()) {
bcc[++bcc_count].push_back(u);
return;
}
int child_count = 0;
for (int v : adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
if (++child_count > 1 || u != root) is_cut[u] = true;
bcc_count++;
do {
bcc[bcc_count].push_back(sta[top--]);
} while (sta[top + 1] != v);
bcc[bcc_count].push_back(u);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
if (u != v) add_edge(u, v);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
root = i;
tarjan(i);
}
}
printf("%d\\n", bcc_count);
for (int i = 1; i <= bcc_count; ++i) {
printf("%lu ", bcc[i].size());
for (int v : bcc[i]) {
printf("%d ", v);
}
printf("\\n");
}
return 0;
}LCA最近公共祖先
Tarjan 算法是一个离线算法，即不能动态的修改输入的图。
思路是先输入图，再把所有的查询作为虚拟边建立查询图。
根据回溯的思想来看，我们找到的点对LCA是不断往上的。
了解一个特性：如果我搜完了一个子树，那么之后的点的lCA就和这个子树完全无关了。
那什么时候和子树有关，就是两个点都在其最小子树内，此时这个子树的根就是它们的LCA。
这种标记形式的LCA什么时候变化？
当我检查完一颗子树，已经处理掉了子树内的所有情况，此时往上回溯到了比它更大的子树时，这些已经访问过的节点可能的LCA就变成这个更大子树的根了。
算法步骤(DFS内)：
- dfs步骤
- 将当前点标记为LCA标准点（和并查集原理相同）
- 检查查询边，如果要查询的边已经访问过（有lCA标准点）他俩的LCA就是这个点
- 如果没有访问过，就不处理
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
class Edge
{
public:
int toVertex, fromVertex;
int next;
int LCA;
Edge() : toVertex(-1), fromVertex(-1), next(-1), LCA(-1) {};
Edge(int u, int v, int n) : fromVertex(u), toVertex(v), next(n), LCA(-1) {};
};
const int MAX = 100;
int head[MAX], queryHead[MAX];
Edge edge[MAX], queryEdge[MAX];
int parent[MAX], visited[MAX];
int vertexCount, queryCount;
int find(int x)
{
if (parent[x] == x){
return x;
}
else{
return parent[x] = find(parent[x]);
}
}
void tarjan(int u)
{
parent[u] = u;
visited[u] = 1;
for (int i = head[u]; i != -1; i = edge[i].next)
{
Edge &e = edge[i];
if (!visited[e.toVertex])
{
tarjan(e.toVertex);
parent[e.toVertex] = u;
}
}
for (int i = queryHead[u]; i != -1; i = queryEdge[i].next)
{
Edge &e = queryEdge[i];
if (visited[e.toVertex])
{
queryEdge[i ^ 1].LCA = e.LCA = find(e.toVertex);
}
}
}
int main()
{
memset(head, 0xff, sizeof(head));
memset(queryHead, 0xff, sizeof(queryHead));
cin >> vertexCount >> queryCount;
int count = 0;
for (int i = 0; i < vertexCount - 1; i++)
{
int start = 0, end = 0;
cin >> start >> end;
edge[count] = Edge(start, end, head[start]);
head[start] = count;
count++;
edge[count] = Edge(end, start, head[end]);
head[end] = count;
count++;
}
count = 0;
for (int i = 0; i < queryCount; i++)
{
int start = 0, end = 0;
cin >> start >> end;
queryEdge[count] = Edge(start, end, queryHead[start]);
queryHead[start] = count;
count++;
queryEdge[count] = Edge(end, start, queryHead[end]);
queryHead[end] = count;
count++;
}
tarjan(1);
for (int i = 0; i < queryCount; i++)
{
Edge &e = queryEdge[i * 2];
cout << "(" << e.fromVertex << "," << e.toVertex << ") " << e.LCA << endl;
}
return 0;
}每次检查当前的LCA标记也就是子树中parent[x] == x 的x，以这种类似于并查集的思想，可以让后面的点一起批量转换标记。
tarjan的思路在于一个标记点，类似于之前的low一样，额外的辅助标记带来的独特作用。
