Tarjan算法可以应用在求解 强连通分量，缩点，桥，割点，双连通分量，LCA等
关于Tarjan的算法讲解我感觉这篇讲的挺不错
@[toc]
对于一个连通图，如果任意两点至少存在两条点不重复路径，则称这个图为点双连通的（简称双连通）；如果任意两点至少存在两条边不重复路径，则称该图为边双连通的。点双连通图的定义等价于任意两条边都同在一个简单环中，而边双连通图的定义等价于任意一条边至少在一个简单环中。对一个无向图，点双连通的极大子图称为点双连通分量（简称双连通分量），边双连通的极大子图称为边双连通分量。
强连通分量
我粗略提一下里面的参量：
dfn[]表示该节点在DFS的过程中第一次搜索到的次序（也就是第几个遍历到的点）
low[]一开始和dfn[]相等，但在回溯过程中不断维护，最终成为这个强连通分量中dfn的最低值
节点u是某个强连通分量的根等价于dfn[u]和low[u]相等
代码
void Tarjan(int u)
{
vis[u]=1;
low[u]=dfn[u]=cnt++;
for(int i=0;i<mp[u].size();i++)
{
int v=mp[u][i];
if(dfn[v]==0)
{
Tarjan(v);//如果这个点还没访问过，从这点继续开始找
low[x] = min(low[x],low[v]);
}
if(vis[v]==1)low[u]=min(low[u],dfn[v]);//更新时间戳
}
if(dfn[u]==low[u])
{
sig++;
}
} 题目
tarjan求割点
割点概念
割点：无向连通图中，去掉一个顶点及和它相邻的所有边，图中的连通分量数增加，则该顶点成为割点
求割点可以不用栈结构
流程
对于根节点，如果有两个以上的子树就说明是割点，因为取出后，子树就会分离
对于非根节点，对于边(u,v)，如果low[v]>=dfn[u]，此时u就是割点
tarjan(u,r)
u:表示当前点
r表示的是树的root
所以r不变，变的是u
代码：
child用来统计孩子数目
cut[x]:表示x是否为割点
// u:当前点 r：本次搜索树的root
void tarjan(ll u, ll r) {
dfn[u] = low[u] = ++deep;
ll child = 0;
for (unsigned i = 0; i < g[u].size(); i++) {
ll v = g[u][i];
if (!dfn[v]) {
tarjan(v, r);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && u != r)cut[u] = 1;//不是根而且他的孩子无法跨越他回到祖先
if (r == u)child++; //如果是搜索树的根，统计孩子数目
}
low[u] = min(low[u], dfn[v]);//已经搜索过了
}
if (child >= 2 && u == r)//如果根节点的子树数量大于等于2 ,将根节点去掉之后两颗子树就分离了
cut[r] = 1;
}
求无向图的割边／桥
理解：
割边:在一个无向图中,去掉一条边(u, v),可以使图的连通分量增多的边, 就是割边,也称做桥
原理：利用tarjan算法, 对于一条边的起点u,终点v,如果满足条件 low[v] > dfn[u], 那么(u, v)就是一条割边, 因为这意味着不存在其他的边使得v可以回到u, 那么割掉就使图分离了.
需要注意的是跟割点不同, 没有等于号, 否则说明存在其他边回到起点, 那么就不是割边。
tarjan(int u,int pre)//pre表示u的父亲节点
代码：
if(!dfn[v])
{
Tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v]>dfn[u]) //isbridge[v]表示在树中，以v为儿子结点的边是否为桥
{
isbridge[v] = 1;
sum_bridge++;//桥的数量加一
}
}
else
low[u] = min(low[u], dfn[v]); 强连通分量缩点
缩点的作用：
1.可以把一个有向带环图，变成一个有向无环图（DAG），（因为我们把环给缩成一个集体）这样我们就可以直接当做无环图做就可以
2.可以算缩点后每个点的出度
图来自
大致流程：
在用Tarjan求完强连通分量后，可以用一个数组color进行标记，将同一个连通分量的点标记为相同数值，这样再遍历一遍所有边之后，如果有个边u->v的两侧不是一个数值，说明不再一个连通分量，则就从u所在颜色向v所在颜色生成一个边，（也就是u所在的连通分量向v所在的连通分量生成一条边），最后这些新生成的边就是组成新的图就是缩点后的图。。
我们可以在此基础上计算缩点后的出入度
代码：
const int MAXN = 5e3 + 20;
const int MAXM = 1e6 + 10;
int head[MAXN], cnt, tot, dfn[MAXN], low[MAXN], color[MAXN], col;
bool vis[MAXN];
int degree[MAXN];
stack<int> stc;
int n, m;
struct Edge {
int to, next, dis;
}edge[MAXM << 1];
void add_edge(int u, int v, int dis) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
void Tarjan(int x) {
vis[x] = 1;
dfn[x] = low[x] = ++tot;
stc.push(x);
for(int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to;
if (!dfn[to]) {
Tarjan(to);
low[x] = min(low[x], low[to]);
} else if( vis[to] ) {
low[x] = min(low[x], dfn[to]);
}
}//以上为正常的tarjan求强连通分量
if(dfn[x] == low[x]) {
col ++;
while(true) {
int top = stc.top();//栈中最上面的点
stc.pop();
color[top] = col; //给同一连通分量的点上相同的颜色，相当于缩点
vis[top] = 0;
// cout << top << " ";
if(top == x) break; //遍历完后退出
}
//cout << endl;
}
}
void solve(){
for(int i = 1; i <= n; ++i) {
if(!dfn[i])
Tarjan(i);
}
for(int x = 1; x <= n; ++x) { //遍历 n个节点
for(int i = head[x]; i; i = edge[i].next) { //缩点后 每个点的出度
int to = edge[i].to;
if(color[x] != color[to]) {
degree[color[x]] ++;//计算出度
}
}
}
}
void init () {
cnt = 1;
tot = 0;
col = 0;
memset(vis, 0, sizeof(vis));
memset(head, 0, sizeof(head));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(degree, 0, sizeof(degree));
memset(color, 0, sizeof(color));
while(!stc.empty()) stc.pop();
}
int main () {
std::ios::sync_with_stdio(false);
cin.tie(0);
while(cin >> n && n) {
cin >> m;
init();
int x, y;
for(int i = 1; i <= m; ++i) {
cin >> x >> y;
add_edge(x, y, 0);
}
solve();
}
return 0;
} 例题
The Bottom of a Graph Poj 2553
Tarjan求LCA
关于LCA本人博客讲解
例题
双连通分量
点双连通图
若一个无向连通图不存在割点，则称它为“点双连通图”。
边双连通图
若一个无向连通图不存在割边，则称它为“边双连通图”。
京公网安备 11010502036488号