$Tarjan$的学习笔记

一，$tarjan$概述：

（1）定义：

$~~~~~~~~$$tarjan$是基于深度优先搜索的一种算法，求解图的连通性等问题，巧妙地利用了对图进行深搜时产生的搜索树上的边。

（2）$tarjan$中的几种边：

$~~~~~~~~$树边：父亲与孩子的边。

$~~~~~~~~$前向边：祖先到孩子的边（树边属于特殊的前向边）。

$~~~~~~~~$后向边：孩子到祖先的边（与前向边相反）。

$~~~~~~~~$横叉边：这种边只有在有向图时才有，两个在搜索树上无祖宗、子孙关系的点之间的边。

$~~~~~~~~$在$tarjan$中，我们只关心树边和后向边。

二，$tarjan$应用一：求解有向图的强联通分量（$SCC$）（然后可以缩点）

（1）有向图的强联通分量（$SCC$）的定义：

$~~~~~~~~$在有向图中，如果两个顶点$u$，$v$存在$u→v$和$v→u$，那么则称$u$，$v$强连通。

$~~~~~~~~$如果有向图的任意两个顶点都强连通，则称为强连通图。

$~~~~~~~~$有向非强连通图的极大强连通子图，称为强连通分量。

（2）算法思路：

$~~~~~~~~$求解有向图的强联通分量时，最重要的是后向边，因为如果存在后向边$u→v$（根据定义，此时一定有$v→u$，为树枝边构成），那么$u$、$v$一定在同一个强连通分量中，那么，如何求解一条边是否为后向边呢？

$~~~~~~~~$首先，我们定义一个数组$dfn$，表示第$u$个节点是第几个被遍历到的（即时间戳）。

$~~~~~~~~$接着，我们可以定义一个栈$s$，其中的元素为当前搜索树上的点，那么如果存在一条后向边$u→v$，那么此时$v$一定在栈中。

$~~~~~~~~$于是我们再定义一个$vis$数组，就可以轻松找到$v$是否在栈里面了（入栈时$vis$变为$1$，出栈时$vis$变为$0$），这样子我们就可以找到两个点是否为强联通的了。

$~~~~~~~~$那么，怎么把一个$SCC$的所有点都找出来呢？

$~~~~~~~~$我们可以定义一个新的数组，$low$。$low[u]$表示从$u$出发最多只通过一条后向边能回溯到最小的$dfn$值。（注意，是从$u$出发，也就是说是从$u$以及它的子树回溯的最早的$dfn$值）

$~~~~~~~~$显然，若$u→v$是一个后向边，那么$v$是$u$在搜索树上的祖先，那么，$low[u]=min(low[u],dfn[v])$。而对于$v→u$路径上的每一个节点$w$，$w$和$v$、$u$属于同一个$SCC$，那么$low[w]=min(low[w],dfn[v])$。

$~~~~~~~~$那么，怎么用代码实现以上的步骤，对$low$数组进行更新呢？

$~~~~~~~~$我们可以在$dfs$内进行回溯时，判断一下当前搜索的节点$u$能到达的节点$v$中，是否有$v$也在栈中，如果在，那么对$low$数组进行更新，即$low[u] = min(low[u], dfn[v])$（此时$u→v$为后向边）。

$~~~~~~~~$另外，如果$u→v$为一条树边，那么$low[u]=min(low[u],low[v])$。

$~~~~~~~~$而在$u$所有的子树搜索完后，若$low[u]$依旧等于$dfn[u]$，则意味着节点$u$为它所在的$SCC$中第一个搜索到的节点，它无法回溯到$dfn$值比它小的节点，那么此时在栈中比$u$先出栈的元素一定就是和$u$在同一$SCC$中的。

$~~~~~~~~$那么，将栈中的比$u$先出栈的元素和$u$依次出栈，再用一个数组$color$对其进行标记（表示同属一个$SCC$），即可。

$~~~~~~~~$如果要进行缩点的话，那么所有$color$数组值一样的点可以看作一个大点，缩点后可以重新建图，或进行其他操作。

$~~~~~~~~$时间复杂度：$O(N+M)$，每个点出栈一次，进栈一次，每条边被访问一次。

（3）代码+注释：

#include<bits/stdc++.h>
using namespace std;
const int N=10000+9,M=10000+9;
stack<int> s;
int dfn[N],low[N],head[N],f[N];
bool vis[N];
int color[N];
int tot,at,sum;
struct node{
    int to,nt;
}a[M];
int n,m;
void add(int x,int y){
	a[++at].to=y,a[at].nt=head[x],head[x]=at;
}
void tarjan(int u){
    dfn[u]=low[u]=++tot;
    vis[u]=1;
    s.push(u);
    for(int i=head[u];i;i=a[i].nt){
        int v=a[i].to;
        if(!dfn[v]){//树边
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]){//后向边
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u])//u为它所在的SCC中第一个搜索到的节点
    {
        sum++;
        while(1){
            int now=s.top();
            s.pop();
            vis[now]=0;
            color[now]=sum;
            if(now==u) break;
        }//依次出栈，进行标记
    }
}

int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++){//如果当前节点未被搜索，则从此节点开始搜索
        if (!dfn[i])tarjan(i);
    }
    return 0;
}

三，$tarjan$应用二：求解无向图的割点

（1）无向图的割点的定义：

$~~~~~~~~$若删除一个点（以及和它关联的边）后，原先的图分裂成两个及以上的不相连的图，则称那个点为割点。

（2）算法思路：

$~~~~~~~~$首先，我们思考一下，在搜索树上，一个点满足什么条件的时为割点？

$~~~~~~~~$①如果这个点为搜索树的根节点，那么若有两个及以上的子树无法到达除这个点外的点，那么把这个点删掉后，就会产生多个不相连的图。

$~~~~~~~~$②如果这个点不为搜索树的根节点，那么只要有一个子树无法到达除这个点外的点，那么把这个点删掉后，就会产生不相连的图。

$~~~~~~~~$也就是说，在进行搜索时，如果有$u→v$，并且$v$没有被搜索过，那么对$v$进行搜索。

$~~~~~~~~$回溯后，若$low[v]<=dfn[u]$，那么就代表节点$v$为根节点的搜索树上的所有点都无法回溯到时间戳比$u$跟小的点，则代表删除$u$后，这个子树间不能同除了$u$和这个子树上的点以外的点相连，若符合上述条件，则$u$为割点。

$~~~~~~~~$那么，具体的$tarjan$代码只需要在求$SCC$的代码上进行一些小修改即可

$~~~~~~~~$因为我们只关心一个点能回溯到的$dfn$的最小值，那么在搜索到$u$时，若存在$u→v$，且$v$没有被搜索过，那么就按照上文说的进行，否则则对$low[u]$值进行更新：$low[u]=min(low[u],dfn[v])$。

（3）代码+注释：

#include<bits/stdc++.h>
using namespace std;
const int N=10000+9,M=10000+9;
int n,m;
struct node{
	int to,nt;
}a[M*2];
int head[N],at;
void add(int x,int y){
	a[++at].to=y,a[at].nt=head[x],head[x]=at;
}

int dfn[N],low[N];
int num=0;
int root;
bool vis[N];
void tarjan(int u){
	dfn[u]=low[u]=++num;
	int v;
	int flag=0;
	for(int i=head[u];i;i=a[i].nt){
		v=a[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v]){
				flag++;
				if(u!=root||flag>=2) vis[u]=1;//判断是否符合条件
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}

	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			root=i;
			tarjan(i);
		}
	}

	return 0;
}

四，$tarjan$应用三：求解无向图的割边（桥）

（1）无向图的割边（桥）的定义：

$~~~~~~~~$若删除这条边后，原先的图分裂成两个及以上的不相连的图，则称这条边为割边（也称为桥）。

（2）算法思路：

$~~~~~~~~$首先，我们思考一下，在搜索树上，一个点满足什么条件的时为桥？

$~~~~~~~~$其实和割点需要满足的条件差不多，首先，一个桥在搜索树上一定是一条树边，不然的话割掉它一定不会对图的连通性产生影响。

$~~~~~~~~$但是，显然的是，肯定不是所有树边都为桥，只有在$u→v$，并且$low[v]<dfn[u]$时才成立，因为这样的话，在搜索树上，以$v$为根的子树能通过一条后向边回溯到的点就是在这棵子树上的，把这条边删除后它们就独立出来了。（注意，是$<$，而不是$<=$，因为我们删除的是边）

$~~~~~~~~$不过需要注意的是，因为是无向图，但我们采用链式前向星存图的时候一条边是存为两条有向边的，所以有可能会产生将走过的树边变为后向边情况，这样子就无法求解了。

$~~~~~~~~$不过由于存图相同的边是挨着的，且下标是一奇一偶，因此在使用$v$数组标记割边时，我们应该标记$i$和$i\wedge1$（因为奇数异或$1$为那个数$+1$，偶数为那个数$-1$），这样也可以避免把重边一刀切的情况。

$~~~~~~~~$同理，在走后向边时，也要判断一下，不是的话再更新$low$数组，否则则是在走做过的边。所以在$tarjan$时还要传一个参，表示它是由经过条边达到的，而在初始调用时则传参$0$，所以储存图的链表数组下标从$2$开始。（$0\wedge1=1$）

（3）代码+注释：

#include<bits/stdc++.h>
using namespace std;
const int N=10000+9,M=10000+9;
int n,m;
struct node{
	int to,nt;
}a[M*2];
int head[N],at=1;//从1开始
void add(int x,int y){
	a[++at].to=y,a[at].nt=head[x],head[x]=at;
}
bool vis[N];
int dfn[N],low[N];
int num=0;
void tarjan(int x,int k){
	dfn[x]=low[x]=++num;
	int y;
	for(int i=head[x];i;i=a[i].nt){
		y=a[i].to;
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y]){
                vis[i]=vis[i^1]=1;
			}
		}
		else if(i!=(k^1)) low[x]=min(low[x],dfn[y]);//判断是否走过
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
        add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i,0);
		}
	}
	return 0;
}

五，$tarjan$应用四：求解无向图的点双连通分量（$v-DCC$）（然后可以缩点）

（1）无向图的点双连通分量（$v-DCC$）的定义：

$~~~~~~~~$若一个无向图不存在割点，称它为“点双连通图”，即删除任意一个点都连通。

$~~~~~~~~$无向图的极大点双连通子图称为“点双连通分量”，简称$v-DCC$。

（2）算法思路：

$~~~~~~~~$我们可以在求解割点的时候，同时求解点双连通分量（$v-DCC$），而过程基本同求解割点时一致，不过要注意的是，割点同时属于多个$v-DCC$。

$~~~~~~~~~$我们同求解$SCC$时一样，维护一个栈，在第一次访问节点$u$时，将其入栈。

$~~~~~~~~~$在判定割点时，若有$u→v$，使得$u$为割点，从则栈顶不断弹出节点，直至$u$在栈中的上一个节点，也就是$v$被弹出，（割点同时属于多个$v-DCC$，不用弹出）而弹出的所有节点与节点$u$一起构成一个点双连通分量。

$~~~~~~~~$不过，同求割点不同的是，求解只要$v-DCC$时，只要是满足了$dfn[u]<=low[v]$，就代表找到了一个$v-DCC$。为什么呢？

$~~~~~~~~$首先，求割点时的特判是针对$u$为根节点的情况的，那么我们分类讨论一下：①在搜索时，只有一次满足了这个条件，那么代表此时搜索树上的节点同属一个$v-DCC$。②不止一次满足了，那么$u$就是割点，那么此时访问到的节点就是同属一个$v-DCC$的。

$~~~~~~~~$注意，如果$u$不与任何点相连，那么它独属于一个$v-DCC$，在$tarjan$开始时特判即可。

$~~~~~~~~$最后，如果要进行缩点的话，我们将同属一个$v-DCC$的点加入同一个$vector$数组中，即可。

（3）代码+注释：

#include<bits/stdc++.h>
using namespace std;
const int N=10000+9,M=10000+9;
int n,m;
struct node{
	int to,nt;
}a[M*2];
int head[N],at;
inline void add(int x,int y){
	a[++at].nt=head[x],head[x]=at,a[at].to=y;
}
int dfn[N],low[N];
vector<int> b[N];//储存同属一个v-DCC的点
stack<int> q;
int num=0;
int bt,root;
void tarjan(int u){
	dfn[u]=low[u]=++num;
	q.push(u);
	if(u==root&&head[u]==0){//特判不与任何点联通的情况
		b[++bt].push_back(u);
		return;
	}
	int v;
	for(int i=head[u];i;i=a[i].nt){
		v=a[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v]){
				bt++;
				int x;
				do{
					x=q.top();q.pop();
					b[bt].push_back(x);
				}while(x!=v);
				b[bt].push_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			root=i;
			tarjan(i);
		}
	}
	return 0;
}

六，$tarjan$应用五：求解无向图边双连通分量（$e-DCC$）(然后可以进行缩点)

（1）无向图边双连通分量（$e-DCC$）的定义：

$~~~~~~~~$若一个无向图不存在桥(割边)，称它为“边双连通图”，即删除任意一条边都连通。

$~~~~~~~~$无向图的极大边双连通子图称为“边双连通分量”。($e-DCC$)

（2）算法思路：

$~~~~~~~~$首先，求解的过程基本上同求解割边（桥）的过程差不多，还是老样子，我们用一个栈储存当前已经遍历到且没有找到所在的$e-DCC$的点。

$~~~~~~~~$我们想一想，如果有$u-v$的边为割边且$u→v$为树边，就是意味着此时$v$节点通过除了这条割边外的边访问不到不在它子树内的点，那么以$v$为根节点的子树就同属一个$e-DCC$，而此时$dfn[v]=low[v]$。

$~~~~~~~~$那么，就和求解$SCC$时一样，在$tarjan$的末尾加上一个判断，若符合条件就将栈中在$v$前面的节点和$v$出栈，这些节点就同属于一个$e-DCC$。

$~~~~~~~~$若要进行缩点的话，和之前一样，用数组$color$将出栈的元素标记就可以了。

（3）代码+注释：

#include<bits/stdc++.h>
using namespace std;
const int N=5001,M=10001;
int n,m;
struct node{
	int to,nt;
}a[M*2];
int head[N],at=1;//注意，从1开始
void add(int x,int y){
	a[++at].nt=head[x],head[x]=at,a[at].to=y;
}
int dfn[N],low[N];
bool vis[M*2+100],v[N];
int color[N];
int num=0;
stack<int> q;
int tot;
void tarjan(int u,int k){
	dfn[u]=low[u]=++num;
	q.push(u);
	int v;
	for(int i=head[u];i;i=a[i].nt){
		v=a[i].to;
		if(!dfn[v]){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
		}
		else if(i!=(k^1)) low[u]=min(low[u],dfn[v]);
	}
    //同求解割边一样
	if(low[u]==dfn[u]){//判断是否符合条件
		tot++;
		do{
			v=q.top();q.pop();
			color[v]=tot;
		}while(v!=u);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(1,0);
	}
	return 0;
}