Tarjan算法是一个基于dfs的搜索算法， 可以在O(N+M)的复杂度内求出图的割点、割边和强联通分量等信息。
https://www.cnblogs.com/shadowland/p/5872257.html该算法的手动模拟详细
再Tarjan算法中，有如下定义。
DFN[ i ] : 在DFS中该节点的时间戳
LOW[ i ] : 为i能追溯到最早的时间戳
在一个无向图中，如果有一个顶点，删除这个顶点以及这个顶点相关联的边以后，图的连通分量增多，就称这个点为割点。
割点伪代码：
tarjan(u, father){
Index ++; //当前时间戳++
Dfn[cur] = Index; //当前顶点cur的时间戳
Low[cur] = Index; //当前顶点能访问最早的时间戳， 一开始为自己
for each (u, v) in E // 枚举每一条边
if (v is not visited) // 如果节点v未被访问过, 即Dfn[v] = 0
child++; //v是u的孩子， 把u的孩子记录下来
tarjan(v) // 继续向下找
Low[u] = min(Low[u], Low[v]);
if (Low[v] is equal or bigger than Dfn[u], and u is not thr root)
u is cut point. //如果low[v] >= Dfn[u] 而且u不是根节点， 说明v不能通过u访问到u前面的结点， u是割点！
if (u is root and u have two children)
u is cut point. //如果u是根节点， 那么他至少要有2个或以上的孩子才是割点
if(v is visited) //如果v访问过， 那么更新Low[u] 为 Low[u] 和Dfn[v]的较小值
Low[u] = min(Low[u], Dfn[v]);
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ;
vector<int> G[maxn];
int n, m, root;
int num[maxn], low[maxn],flag[maxn], Index;
set<int> ans;
void dfs(int cur, int father)
{
int child = ; //当前结点孩子数目
Index ++; //当前时间戳++
num[cur] = Index; //当前顶点cur的时间戳
low[cur] = Index; //当前顶点能访问最早的时间戳， 一开始为自己
for(int i = ; i < G[cur].size(); i++) //枚举所有与顶点cur相连的顶点
{
int v = G[cur][i];
if(num[v] == ) //如果没被访问过
{
child++; //那么该结点v就是cur的孩子
dfs(v, cur); //访问该结点v
low[cur] = min(low[v], low[cur]); //更新cur能到达的最早顶点时间戳
if(low[v] >= num[cur] && cur != root) //如果不是根节点， 而且满足low[v] >= num[cur]
{
flag[cur] = ; //那么cur就是割点
}
if(cur == root && child == ) //如果是根节点， 那么至少有2个孩子才是割点
flag[cur] = ;//这里其实是>=2， 但因为dfs搜到第二个孩子就会把该点认为是割点
}
else if(v != father)//如果 v不是cur的父亲， 而且被访问过， 说明v是cur的祖先，要更新low[cur]
{
low[cur] = min(low[cur], num[v]);
}
}
return;
}
int main()
{ int i, j, u, v;
int kase = ;
while(~scanf("%d %d", &n,&m))
{
Index = ;
memset(num,,sizeof(num));
memset(low,,sizeof(low));
memset(flag,,sizeof(flag));
for(int i = ; i < n; i++) G[i].clear();
ans.clear();
for(int i = ; i < m; i++)
{
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
root = ;//标记根节点
dfs(, root);
for(int i = ; i < n; i++)
if(flag[i] == ) printf("%d ", i);
puts("");
}
return ;
} 割点实现代码
割点实现代码
在一个无向图中，如果有一条边，删除这条边以后，图的连通分量增多，就称这个点为割边。
割边伪代码：
tarjan(u, father){
Index ++; //当前时间戳++
Dfn[cur] = Index; //当前顶点cur的时间戳
Low[cur] = Index; //当前顶点能访问最早的时间戳， 一开始为自己
for each (u, v) in E // 枚举每一条边
if (v is not visited) // 如果节点v未被访问过, 即Dfn[v] = 0
tarjan(v) // 继续向下找
Low[u] = min(Low[u], Low[v]);
if (Low[v] is bigger than Dfn[u])
E(u,v) is a cut edge// 割边的条件为， Low[v] > dfn[u]
// 即如果不通过这条边， 去不到他的祖先（包括父亲）的点
if(v is visited) //如果v访问过， 那么更新Low[u] 为 Low[u] 和Dfn[v]的较小值
Low[u] = min(Low[u], Dfn[v]);
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ;
vector<int> G[maxn];
int n, m, root;
int num[maxn], low[maxn],flag[maxn], Index;
void dfs(int cur, int father)
{
// printf("cur : %d father : %d\n", cur, father);
//求割边则不需要记录孩子数目
Index ++; //当前时间戳++
num[cur] = Index; //当前顶点cur的时间戳
low[cur] = Index; //当前顶点能访问最早的时间戳， 一开始为自己
for(int i = ; i < G[cur].size(); i++) //枚举所有与顶点cur相连的顶点
{
int v = G[cur][i];
if(num[v] == ) //如果没被访问过
{
dfs(v, cur); //访问该结点v
low[cur] = min(low[v], low[cur]); //更新cur能到达的最早顶点时间戳
if(low[v] > num[cur]) //如果不是根节点， 而且满足low[v] >= num[cur]
{
printf("%d %d\n", cur, v);
} }
else if(v != father)//如果 v不是cur的父亲， 而且被访问过， 说明v是cur的祖先，要更新low[cur]
{
low[cur] = min(low[cur], num[v]);
}
}
return;
} int main()
{
// freopen("1.txt","r", stdin);
int i, j, u, v;
int kase = ;
while(~scanf("%d %d", &n,&m))
{
Index = ;
memset(num,,sizeof(num));
memset(low,,sizeof(low));
memset(flag,,sizeof(flag));
for(int i = ; i < n; i++) G[i].clear();
for(int i = ; i < m; i++)
{
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
root = ;//标记根节点
dfs(, root); puts("");
}
return ;
}
割边实现代码
在一个有向图G中，有一个子图，这个子图任意2个点都互相可达，我们就叫这个子图叫做强连通子图。
有向图的极大强连通子图为强连通分量
强连通分量伪代码
tarjan(u){
DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
Stack.push(u) // 将节点u压入栈中
for each (u, v) in E // 枚举每一条边
if (v is not visted) // 如果节点v未被访问过
tarjan(v) // 继续向下找
Low[u] = min(Low[u], Low[v])
else if (v in S) // 如果节点u还在栈内
Low[u] = min(Low[u], DFN[v])
if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根， 因为该强联通分量中， 该点Low值最小（出现最早）。
repeat v = S.pop
until (u == v) // v是栈顶元素，将v退栈，为该强连通分量中一个顶点， 退栈的所有元素为该强联通分量中的点
// 如果退栈的栈顶元素是u， 说明以v为根的强联通分量已经全部找出。
}
#include <stack>
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = ;
vector<int> G[maxn];
int n , m;
int dfn[maxn], low[maxn], color[maxn], out_degree[maxn];
int dfs_num = , col_num = ;
bool vis[maxn];//标记元素是否在栈中
stack<int> s;
void Tarjan(int u)
{
dfn[ u ] = dfs_num;
low[ u ] = dfs_num++;
vis[u] = true;
s.push(u);
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if( ! dfn[v]) //如果v没有访问过
{
Tarjan( v ); //访问v， 并更新low[u]
low[u] = min(low[v], low[u]);
}
else if(vis[v]) //如果v在栈中
{
low[u] = min(low[u], dfn[v]); //更新low[u]
}
}
if(dfn[u] == low[u])
{
vis[u] = false;
color[u] = col_num;//把强连通分量记录成统一编号、 类似并查集
int t;
for(;;){
int t = s.top(); s.pop();
color[t] = col_num;
vis[t] = false;
if(t == u) break;
}
col_num++;
}
}
int main()
{
scanf("%d %d", &n,&m);
for(int i = ; i < m; i++)
{
int u , v;
scanf("%d %d", &u, &v);
G[u].push_back(v); } //因为图不一定连通， 所以每个顶点都要访问一次
for(int i = ; i <= n; i++){
if(!dfn[i])
Tarjan(i);
} //输出强连通分量
for(int i = ; i < col_num; i++){
for(int u = ; u <= n; u++){
if(color[u] == i) printf("%d ", u);
}
puts("");
} return ;
}
强连通分量实现
部分实现参考《啊哈算法》