Tarjan算法模板

2024-05-08 00:04

文章标签 算法模板 tarjan

本文主要是介绍Tarjan算法模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、最近公共祖先（LCA）

LCA：Least Common Ancestor

P3379 【模板】最近公共祖先（LCA）

#include <bits/stdc++.h>using namespace std;
typedef long long ll;ll quickin(void)
{ll ret = 0;bool flag = false;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')    flag = true;ch = getchar();}while (ch >= '0' && ch <= '9' && ch != EOF){ret = ret * 10 + ch - '0';ch = getchar();}if (flag)    ret = -ret;return ret;
}// 存查询的数据结构 
typedef pair<int, int> P;  // first -- 另一个节点; second -- 查询编号 const int MAX = 5e5 + 3;
int N, M, S;               // N -- 节点数; M -- 查询数; S -- 根节点 
vector<int> G[MAX];        // 存树，按无向图存储 
vector<P> query[MAX];      // 存查询，双向存 
int par[MAX], ans[MAX];    // par[] -- 各节点的父节点; ans[] -- 查询答案，按编号存储 
bool vis[MAX];             // vis[] -- 是否访问该节点 // 并查集初始化 
void init(void)
{for (int i = 1; i <= N; ++i)par[i] = i;
}// 并查集查询 
int find(int x)
{if (par[x] == x)    return x;elsereturn par[x] = find(par[x]);
}// tarjan算法 + 并查集 
void tarjan(int u)
{vis[u] = true;                         // 入u, 标记u// 遍历u的每条边 for (int i = 0; i < G[u].size(); ++i){int v = G[u][i];if (!vis[v])                       // 防止访问父节点 {tarjan(v);par[v] = u;                    // 回u, v指向u }}// 离u, 处理查询 for (int i = 0; i < query[u].size(); ++i){P p = query[u][i];int v = p.first, id = p.second;if (vis[v])    ans[id] = find(v);      // 若v被访问过，则v的根节点即所求 }
}int main()
{#ifdef LOCALfreopen("test.in", "r", stdin);#endifN = quickin(), M = quickin(), S = quickin();for (int i = 0; i < N - 1; ++i){int a, b;a = quickin(), b = quickin();G[a].push_back(b);               // 双向存边 G[b].push_back(a);}for (int i = 0; i < M; ++i){int a, b;a = quickin(), b = quickin();query[a].push_back(P(b, i));     // 双向存查询; i -- 查询编号 query[b].push_back(P(a, i));}init();tarjan(S);for (int i = 0; i < M; ++i)cout << ans[i] << endl;return 0;
}

二、强连通分量（SCC）

SCC：Strongly Connected Component

B3609 [图论与代数结构 701] 强连通分量

1、基本概念

搜索树:对图深搜时，每个节点仅访问一次，节点按被访问的顺序和访问时经过的有向边组成搜索树。
有向边的分类：

树边：搜索树中的边
返祖边：指向祖先节点的边
横插边：右子树指向左子树的边
前向边：指向子孙节点的边

定理1：返祖边与树边必定构成环，横插边可能与树边构成环，前向边无用。
定理2：强连通分量以树的形式存在于搜索树中，每个强连通分量都有一个根，其余节点都在根的子树中。

#include <bits/stdc++.h>using namespace std;
typedef long long ll;ll quickin(void)
{ll ret = 0;bool flag = false;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')    flag = true;ch = getchar();}while (ch >= '0' && ch <= '9' && ch != EOF){ret = ret * 10 + ch - '0';ch = getchar();}if (flag)    ret = -ret;return ret;
}const int MAX = 1e4 + 3;
int N, M;                       // N -- 节点数; M -- 边数 
vector<int> G[MAX];             // 存有向图 
int dfn[MAX], low[MAX], tot;    
/*
dfn[] -- 时间戳，各节点第一次被访问的顺序（也可以起到vis[]的作用） 
low[] -- 从该节点出发，能访问到的最早的时间戳
tot -- 更新时间戳 
*/
stack<int> S;                   // 将节点按时间戳压栈 
bool instk[MAX];                // 该节点是否在栈中 
vector<vector<int>> ans;        // 存储强连通分量 void tarjan(int u)
{// 入u，盖戳，入栈 dfn[u] = low[u] = ++tot;S.push(u), instk[u] = true;// 遍历u的每条边 for (int i = 0; i < G[u].size(); ++i){int v = G[u][i];if (!dfn[v])                       // 未访问过v（在搜索树中，v是u的孩子） {tarjan(v);low[u] = min(low[u], low[v]);  // 回u，更新low }else if (instk[v])                 // 访问过v，且在栈中（在搜索树中，v是u的祖先） {low[u] = min(low[u], dfn[v]);}}// 离u，处理强连通分量 if (dfn[u] == low[u]){vector<int> scc;int t;do{t = S.top();S.pop(), instk[t] = false;scc.push_back(t);} while (t != u);sort(scc.begin(), scc.end());ans.push_back(scc);}
}bool cmp(const vector<int> &a, const vector<int> &b)
{return a[0] < b[0];
}int main()
{#ifdef LOCALfreopen("test.in", "r", stdin);#endifN = quickin(), M = quickin();for (int i = 0; i < M; ++i){int a, b;a = quickin(), b = quickin();G[a].push_back(b);                  // 存储有向边 }// 图未必是连通的 for (int i = 1; i <= N; ++i){if (!dfn[i])tarjan(i);}sort(ans.begin(), ans.end(), cmp);cout << ans.size() << endl;for (int i = 0; i < ans.size(); ++i){for (int j = 0; j < ans[i].size(); ++j){cout << ans[i][j] << ' ';}cout << endl;}return 0;
}