Tarjan

Tarjan算法是图论中非常常用的算法之一，能解决强连通分量，双连通分量，割点和桥，求最近公共祖先（LCA）等问题。

Tarjan 算法是基于深度优先搜索的算法，用于求解图的连通性问题。

割点

如果从图中删除节点 \(x\) 以及所有与 \(x\) 关联的边之后，图将被分成两个或两个以上的不相连的子图，那么称 \(x\) 为图的割点。

如3、5就是图的割点

桥/割边

如果从图中删除边 \(e\) 之后，图将分裂成两个不相连的子图，那么称 \(e\) 为图的桥/割边。

如图中边 \((3,5)\) 就是图的割边

实现

几个定义

强连通分量 :
对于一个分量，若任意两个点相通，则称为强连通分量。

树边 :
对于一个图的dfs树，它的树边便是此图的树边。

返祖边 :
对于一个图的dfs树，可以使得儿子节点返回到它的祖先的边为返祖边。

横插边 :
对于一个图的dfs树，可以使得一个节点到达另一个节点且它们互不是祖先的边为横插边。

连通

连通：无向图中，从任意点 \(i\) 可到达任一点 \(j\) 。
强连通：有向图中，从任意点 \(i\) 可到达任一点 \(j\)。
弱连通：把有向图看作无向图时，从任意点i可到达任一点 \(j\)。

强连通分量

整个图并不是强连通的，但是在某些局部区域符合强连通的要求，如下图，整张图不算是强连通，但局部还是能满足强连通条件的。

时间戳

时间戳是用来标记图中每个节点在进行dfs时被访问的顺序，可以理解成一个由小到大的序号（类似于dfs序）。

搜索树

在无向图中，以某一个节点 \(x\) 出发进行dfs，每一个节点只访问一次，所有被访问过的节点和边构成一棵树，称之为“无向连通图的搜索树”。

追溯值

追溯值用来表示从当前节点 \(x\) 能够访问到的所有节点中，时间戳最小的值。
能够访问到的节点其需要满足下面的条件之一：

• 以 \(x\) 为根的搜索树的所有节点。
• 通过一条非搜索树上的边，能够到达搜索树的所有节点。

代码

dfn：第 \(i\) 个节点的时间戳。

low：第 \(i\) 个节点最多经过一条返祖边所能到达的最小时间戳。

s：一个栈,用来储存当前还未确定但已经扩展过的点。

b：第 \(i\) 个节点是否遍历过。

ans：答案计数。

void tarjan(int 当前点){
    这个点的low=dfn=时间戳;
    将这个点入栈;
    标记这个点入栈;
    for(这个点连接的所有边){
        if(目标点没有被访问过){
            tarjan(目标点);
            更新当前点的low; 
        }else if(目标点被访问过){
            更新当前点的low; 
        } 
    }
    if(当前点的low==dfn){
        将这个点及栈以上的点出栈，标记成一个强连通分量; 
        ans++; 
    } 
}

int dfn[100010],low[100010];
int n,m,num=0,ans=0;
vector<int>v[100010];
stack<int>s;
void tarjan(int x){
	num++;
    dfn[x]=low[x]=num;
    st.push(u);
    b[x]=1;
    for(int i=0;i<v[x].size();i++) {
        int nn=v[x][i];
        if(!dfn[nn]){
            tarjan(nn);
            low[x]=min(low[x],dfn[nn]);
        }else if(b[nn]){
        	low[x]=min(low[x],dfn[nn]);
		}
    }
    if(low[u]==dfn[u]){
    	while(!s.empty()&&s.top()!=u){
            vis[s.top()]=0;
            s.pop(); 
        }
        b[u]=0;
        s.pop();
        ans++;
	}
}