Tarjan算法

Tarjan是一种求强连通分量、双连通分量的常用算法。
其拓展例如求缩点、割点、割桥以及2-SAT等都是非常实用的

概念

如果有向图G的任意两个顶点都互相可达，则称G是一个强连通图。

强连通分量：它是一个图的强连通子图，并且加入其他任意顶点集合都会导致它不再强连通。

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。

变量含义

用dfn[ ]数组，表示当前这个点在dfs中是第几个被搜到的。
用low[ ]数组，表示当前这个点以及他的子孙节点连的所有点中dfn最小的值。
用stack s，表示当前所有可能能构成强连通分量的点。
用inStack[ ]数组，表示一个点是否在栈中。

算法步骤

我们来考虑这几个数组的用处以及算法的具体过程。

现在开始遍历点u：

1、首先初始化dfn[u] = low[u] = 第几个被dfs到

2、将u存入stack[ ]中，并将vis[u]设为true

3、遍历u的每一个能到的点，如果这个点dfn[ ]为0，即仍未访问过，那么就对点v进行dfs，然后low[u]=min{low[u],low[v]}

4、假设我们已经dfs完了u的所有的子树，那么之后无论我们再怎么dfs，u点的low值已经不会再变了。

注意：tarjan一遍不能搜完所有的点，因为存在孤立点或者其他。所以我们要对一趟跑下来还没有被访问到的点继续跑tarjan。

void tarjan(int u)
{
	int v;
	
    dfn[u] = low[u] = index++;//标记是第几个被dfs 
    inStack[u] = true;//标记该点已经被访问 
    s.push(u);//把当前点入栈 
    
    for(int i = 0;i < g[u].size();i++)//跑一遍与该点相连的点
    {
        v = g[u][i];//u为当前点，v为被连接的点 
        if(!dfn[v])//如果v也没有被搜过 
        {
            tarjan(v);//那么，对v点进行tarjan() 。（这里有点类似递归的思想） 
            low[u] = min(low[u], low[v]);//这时候u v 都已经被搜过了，我们取他们的祖先的最小 
        }
        else if(inStack[v])//如果v已经被搜过了
            low[u] = min(low[u], dfn[v]);//那么直接取他们的最小值
    }
    if(dfn[u] == low[u])//low等于dfn，则为强连通分量的根，或者本身（一个点）为一个强连通分量 
    {
        num++;
        while(v != u)//弹栈直到
        {
        	v = s.top();//等于栈顶 
    		s.pop();//弹栈 
    		color[v] = num;//染色,num的值等于强连通分量的个数 
        } 
    }
}

如何判断这个点有没有被访问过？
判断依据：看看它的dfn是否为0！

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

个人理解

tarjan算法是基于有向图上的dfs，每个点我们都要搜一遍，对于搜过的点我们就标记它已经搜过了，之后就不再搜它了，其中搜索类似递归的调用tarjan()算法。
在搜索的过程，我们对每个点都搜与它相连的点，如果搜到后面发现它连着祖先，说明有环，这时候修改low，把这个环里面的low都改成他们中被dfs的最小值，搜完到底后回溯，如果遇到根节点，就num++，表示强连通分量的个数加一，然后把这个强连通分量的所有点都弹出栈。

最后num的值就是强连通分量的个数。

时间复杂度

运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。

代码：求强连通分量个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e6+5;
const int INF = 0x3f3f3f3f;

int dfn[maxn];//第几个被dfs到
int low[maxn];//这个点以及他连的所有点中，dfn最小的值。
int index;//第几个被dfs的值

bool inStack[maxn];//表示一个点是否在栈中 
vector <int> g[maxn];//邻接表存的图 
stack <int> s;//当前所有可能能构成强连通分量的点 

int color[maxn];//颜色 
int num;//颜色 

void tarjan(int u)
{
	int v;
	
    dfn[u] = low[u] = index++;//标记是第几个被dfs 
    inStack[u] = true;//标记该点已经被访问 
    s.push(u);//把当前点入栈 
    
    for(int i = 0;i < g[u].size();i++)//跑一遍与该点相连的点
    {
        v = g[u][i];//u为当前点，v为被连接的点 
        if(!dfn[v])//如果v也没有被搜过 
        {
            tarjan(v);//那么，对v点进行tarjan() 。（这里有点类似递归的思想） 
            low[u] = min(low[u], low[v]);//这时候u v 都已经被搜过了，我们取他们的祖先的最小 
        }
        else if(inStack[v])//如果v已经被搜过了
            low[u] = min(low[u], dfn[v]);//那么直接取他们的最小值
    }
    if(dfn[u] == low[u])//low等于dfn，则为强连通分量的根，或者本身（一个点）为一个强连通分量 
    {
        num++;
        while(v != u)//弹栈直到
        {
        	v = s.top();//等于栈顶 
    		s.pop();//弹栈 
    		color[v] = num;//染色,num的值等于强连通分量的个数 
        } 
    }
}
int main()
{
	int n, m;//n表示点的个数，m表示边的条数 
	while(scanf("%d %d",&n, &m) && (n || m))
	{
		memset(dfn,0,sizeof(dfn));//清除之前的信息 
		memset(low,0,sizeof(low));//清除之前的信息 
		index = num = 0;
		
		for(int i = 0;i <= n;i++)
			g[i].clear();//清除上次的图
			
		while(m--)//所有的边 
		{
			int a, b;
			scanf("%d %d", &a, &b);//a b相连 
			g[a].push_back(b);//建邻接表 
		}
		
		for(int i = 1;i <= n;i++)//对于每一个顶点 
			if(!dfn[i])//如果dfn[i]为0，说明没有被访问过，那么我就对它进行tarjan() 
				tarjan(i);
		
		printf("%d\n", num);//输出强连通分量的个数 
	} 
	return 0;
} 

缩点

任意的有向图都可以分解成若干个不相交的强连通分量，这就是强连通分量分解。而我们可以把分解后的强连通分量缩成（看作）一个顶点（也就是缩点），就得到了一个DAG（有向无环图）

从上面的代码中可以看到，我们对图进行了染色。在缩点的时候，我们只需要把同一颜色的点权加到一块，然后把该颜色指向不同颜色的边建好就可以了。

割点

割点：无向图中，删除了这个点以及与它相连的所有的边之后，图会分裂成两个或两个以上的子图。

这和之前强连通分量中的tarjan类似
如果这个点的dfn比low要小，说明他的子树中没有能够到达他祖先的点，他是这个双连通分量的一个割点，但要加一个特判，如果根节点有两个及以上的儿子，那么他也是割点。

代码如下：

参考资料

博客
https://blog.csdn.net/xuziling_/article/details/79967369

百度百科
https://baike.baidu.com/item/tarjan算法

[洛谷日报第23期]初探tarjan算法 https://www.sohu.com/a/245954819_100201031

《挑战程序设计竞赛》经验总结 P320