Tarjan是什么？
Tarjan算法是由Robert Tarjan发明的可以求有向图中强连通分量的算法。
Tarjan算法可以解决强连通分量、双连通分量、割点和桥、LCA等问题，这里介绍用它来找强连通分量。
有向图：由有向边构成的图，与之对应的是无向图。
强连通分量：如果两个顶点可以相互到达，则称两个顶点强连通（strongly connected）。如果有向图G的每两个顶点都强连通，则称G是一个强连通图。非强连通有向图的极大强连通子图，称为强连通分量（strongly connected components）。
算法介绍
下图中，子图[1, 2, 3, 4]为强连通分量，顶点1、2、3、4两两可达，[5]、[6]也是两个强连通分量。
在Tarjan算法中我们维护如下的变量：
vector
伪代码：
void 
C++实现
//输出强连通分量的数量及包含的点 

强连通分量
什么是强连通图？

如果一个有向图中，存在一条回路，所有的结点至少被经过一次，这样的图为强连通图。


什么是强连通分量？

在强连通图的基础上加入一些点和路径，使得当前的图不再强连通，称原来的强连通的部分为强连通分量。

求强连通分量有何作用？

在进行对其他图论问题求解前，利用强连通分量的知识可以把图中强连通的点缩为一个点，减少接下来其他图论操作的计算。

在某些特定的环境下，求强连通分量变相地得出了图中的环以及环的长度。
利用Tarjan算法求强连通分量
Tarjan算法的基本思路
首先考虑强连通分量的性质，即存在一条回路能从初始点又回到初始点。在这个查找的过程中，可以对经过的节点标记，当发现某一个节点连向的点正好以及被标记过，则说明找到了一条回路，而这个回路上的所有点构成了一个强连通分量。为了保存这个强连通分量，我们需要知道这条路上有哪些点，而此时，栈就是一种适合该算法的数据结构。对于每次搜索的点，我们都加入栈中，遇到回路时，在把栈中的元素逐个弹出，记录他们的起始节点，直到栈中弹出的元素正好是起始节点时，结束弹栈，继续搜索其他连通分量。在这个过程中，所有点和边都被遍历一次，所以最终的时间复杂度是O（N+E）
Tarjan算法的实现
为了实现这个过程，Tarjan算法需要装备如下几样东西：

记录搜索顺序的数组dfn

记录所属强连通分量的数组low

表示某个结点是否在栈中的数组instack

一个栈存搜索路径

从上面对Tarjan算法的描述中，很容易看出这个算法是基于深度先搜索实现的。接下来，对Tarjan算法进行逐步的推演。












模板：
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,cntb;
vector<int>edge[101];   
vector<int>belong[101];
bool instack[101];
int dfn[101],low[101];
stack<int>s;
void Tarjan(int u)
{
    ++cnt;
    dfn[u]=low[u]=cnt;
    s.push(u);
    instack[u]=true;
    for(int i=0;i<edge[i].size();i++)
    {
        int v=edge[u][i];
        if(!dfn[v])
        {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
            low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        ++cntb;
        int node;
        do
        {
            node=s.top();
            s.pop();
            instack[node]=false;
            belong[cntb].push_back(node);
        }while(node!=u);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
    }
    Tarjan(1);
    system("pause");
    return 0;
}

强连通分量 Tarjan
前言
其实很早就会用Tarjan打强连通了，但还是有些一知半解，也忘性大，现在总结一下。
强连通分量的定义
假设我们现在有这个图：



很显然这三个点两两之间可以到达，那么我们就称这个图是强连通的。
假设我们多加一个节点



之前的子图强连通，但不是强联通分量，因为它不是最大的强连通子图，而{1,2，3,4}是强连通分量。一个图可能有多个强连通分量，但我们找强连通一定要找尽可能大的，才能称为强联通分量。
那么得出定义：有向图的极大强连通子图,称为强连通分量。
用途
首先为什么要找？

1.常用于有向图的缩点

缩点就是把每个强连通分量变成分别几个点。

比如这个图：



缩点后就变成：



{1,2,3,4}对应3，5、6分别对应2、1（单独构成强连通分量）
比如这道题：

我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有N（<=1000）个袁绍的奸细，将他们从1到N进行编号，同时他们之间存在一种传递关系，即若C[i，j]=1，则奸细i能将消息直接传递给奸细j。

　　现在曹操要发布一个假消息，需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息，问我们至少要传给几个奸细

显然，如果把奸细直接的关系图缩点后，只要求出入度为0的强连通分量个数就行了。
2.解决2-SAT问题（这里先不讲）
Tarjan求强连通分量（缩点）
先给出一些定义：

$dfn[u]$表示$u$的搜索次序（时间戳，就是说$u$是第几个搜到的）

$low[u]$表示$u$及其子孙可以回溯到最小的$dfn$（就是说往下搜可以搜到最早的点）
那么怎么更新$low$?
我们设$v$就是$u$的子孙，并且每次搜索到一个节点就放入栈中（具体待会说，首先知道找到强连通分量就会把强连通分量内节点退栈）
如果$v$未被访问（时间戳=0），根据定义，我们可以更新

$low[u]=min(low[u],low[v])$
如果$v$已被访问且$v$还在栈中，说明这个节点还不能确定是任何强联通分量内的节点，并且出现了一个“环”（至少发现了一个强连通子图）！我们可以更新

$low[u]=min(low[u],dfn[v])$（这里就不要用$low$更新了，因为这里的$low$不一定是当前搜索子树的节点更新而来的，会影响正确性）
我们遍历完$u$的所有子树后，如果发现$low[u]=dfn[u]$，就说明现在栈中在$u$以上的所有节点（包括$u$）构成一个强连通分量，简单来说就是它已经形成一个回路，自然就两两连通。完整性（为什么保证是强连通分量而不是强连通子图）：已遍历所以 有可行节点。
当然，不是从1号节点递归一次就可以了。如果图分为几个不连通的子图，就不能一次跑完，所以要枚举每一个节点跑递归（如果该节点没有跑过）。
算法过程

代码
这里给出重要部分的代码
void tarjan(int u)
{
	dfn[u]=low[u]=++num,st[++top]=u;//dfn和low初始化为搜索次序num，并将u入栈 
	for (int i=head[u];i;i=next[i])//枚举边 
	{
		int v=e[i];
		if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);//如果v未被访问，就继续枚举，并更新low 
		else if (!co[v]) low[u]=min(low[u],dfn[v]);//否则如果v不在栈中（不在栈中等于访问过并还不属于任何强连通分量），并更新low 
	}
	if (low[u]==dfn[u])//如果自己就是根，即low=dfn 
	{
		co[u]=++col; 
		while (st[top]!=u) co[st[top--]]=col;
		top--;
		//退栈并将u以上的所有节点标记为一个强连通分量 
	}
}
//主程序不要忘了枚举每一个节点直到都被访问

如有错误 ，请指教。

本文转自：http://blog.stqdd.com/?p=209


对于有向连通图，如果任意两点之间都能到达，则称为强连通图。如果对于有向图的一个子图是强连通的，则称为强连通子图；

极大的强连通子图称为强连通分量。一个有向图可以有多个强连通分量，一个点也算是强连通分量。强连通分量的术语是strongly connnected components,简称SCC

 

对于无向连通图，如果任意两点之间都有多于一条的路径，则称为双连通图。对于无向图的一个子图是双连通的，则称为双连通子图；

极大的双连通子图称为双连通分量。一个无向图可以有多个双连通分量，一个点也算是双连通分量。双连通分量的术语是biconnected components,简称为BCC

 

强连通分量是针对有向图而言的，从定义出现，我们可以得到一个直观的算法，网上流传的说法是双向遍历求交集，时间复杂度是O(N^2+M). 这里我对此做些简单的解释。为什么要解释呢？因为我总和kosaraju算法的双dfs搞混淆。

（1）因为强连通要求，任意两点之间都可到达，那么我们自然会这么做：任意一点开始深搜，对于该点深搜到的所有的点再次深搜看是否能够返回到原点。因为从这一点开始深搜能够搜索到一个点的集合，这些点集再次向原点深搜，势必会再次得到一个集合，这两个集合求个交集就是一个强连通分量;

void dfs( 原点s）

{


FOR 原点能够连接到的点e

      dfs(e);

      if( e能够到达s)

             加入到强连通分量的集合中。


}

FOR 任意一点开始


if ( 没有搜索过 )

       dfs( 该点 )


分析这样的程序，复杂度大约是N^2+M*alpha ,这里每条边并不是只遍历一次的。

 

举个例子来说明这个根据定义出现得出的低效率算法：



对于此图，我们先用（1）方法来做

从A点出现，搜索



遍历顺序: A



遍历顺序：A B



遍历顺序：A B C



遍历顺序：A (AB) B (BC) C (CD) D



遍历顺序：A (AB) B (BC) C (CD) D (DH) H



遍历顺序：A (AB) B (BC) C (CD) D (DH) H (HG) G



遍历顺序：A (AB) B (BC) C (CD) D (DH) H (HG) G (GF) F

到达F后，无法继续往前走了，此时，从F开始再次dfs看是否能够到达A.



结果图中绿色的线就是从F开始的DFS路线，很明显是不能到达的，所以F不和A在一个SCC中。

返回到G



从G开始DFS，绿色的线就是路径了，也无法到达A,所以G也不和A在一个SCC中。此时注意到，绿色线之前曾经被遍历过，所以此方法复杂度中的M是带有一个常数的。

继续返回至H



从H开始也无法到达A,所以H不是和A一个SCC中。

返回至D

    

D无法到达A

返回至C



可见C无法到达

返回至B，B还有一个儿子没有遍历



而E无法前行了，而E能够到达A,所以E是A的集合的

最后返回B



而B能够到达A,所以B也是A集合

最后返回到A,终结了一个强连通分量，那就是{A,B,E}.

接下来，到达C和F的时候还会分别找到两个强连通分量，这就是这个实现的示意图。

 

通过以上的例子说明了SCC的低效率的解法，那么kosaraju和tarjan算法到达快到哪里了呢？

先说说kosaraju算法把。其时间复杂度是O(N+M);

低效率算法的之所以慢，是因为要判断每个能够到达的点是否能够在到达原点，这就构成了一个双层的循环，N^2的算法了。如果我们能够找到一种方法来高效的解决到达的点是否能否在返回至原点的话，复杂度就会减少很多。

kosaraju是最早提出一种高效的方法来解决这个问题的。我们注意到一个有趣的现象，如果我们把有向边的方向转向的话，强连通分量并不会改变，kosaraju正是利用了这个性质，才规避了判断一个点是否能够到达原点的。到达的点是否能够返回，等价于我们把边反向，判断原点是否能够到达该点。这样，我们只需对每个点做两次dfs就求出SCC了。这样每个点出了第一次必须的dfs外，只需在额外的在一次dfs就可以，这样就比原先的多次dfs，效率提高了很多。

kosaraju算法还有一个优点就是求出来的SCC具有拓扑顺序的性质。kosaraju算法在实现的是否需要两次dfs和一个堆栈的辅助。堆栈记录第一次dfs的时候遍历按照左右中的顺序把节点保存到栈中的。例子如下：



从A出发，stack={F G H D C}



stack={F G H D C E}



stack={F G H D C E B}



stack={F G H D C E B A}

第一次遍历结束

然后从栈顶元素A开始反图上遍历。

从A出现，能够遍历到的点是{A E B},栈弹出这三个点，然后stack = {F G H D C},这其实也是按照缩图后拓扑排序的第一个SCC

从C出发，能够遍历到的点是{C D H},栈弹出这三个点，然后stack={F G},这其实是按照缩图后拓扑排序的下一个SCC

从G出发，能够遍历到的点是{G F},栈弹出这两个点，然后stack={},这就是最后的一个SCC了

缩图后的效果图如下：

    

从这个图中发现，{ABE}是拓扑的第一个点，{CDH}是第二个点，{FG}是第三个点

 

kosaraju算法毕竟需要两次dfs,效率自然没有tarjan算法高。接着介绍下tarjan算法，这个算法的应用非常的广。需要格外注意。

tarjan的主要思想是一次dfs,记录下遍历的编号dfn[i],和low[i](i点可以通过回边连接到的最小的遍历号)，当遍历完一个节点的所有子树后，发现low[i]==dfn[i]时，那么从栈顶开始弹出节点，直到stk[top-1]==i.

 

FOR 对于i的所有孩子节点


if v没有访问过

       dfs(孩子v)

       low[i] = min(low[i],low[v]);

else if i在栈中的话

       low[i] = min(low[i],dfn[v]);


        if low[i]==dfn[i]

             弹出一个SCC

 

这个算法实现简单，也很巧妙。还有一个gabow算法在此先不介绍，之所以介绍了tarjan算法，是因为这个算法在求解无向连通图的双连通分量的时候，也有用武之地。所以接下来要说下无向连通图的双连通分量。

 

对于无向连通图，关于双连通分量有两个概念，一个是点连通分量，一个是边连通分量。这两个又有区别又有联系。

点连通分量，是点连通度大于1的极大连通子图。其对应于割点，即去掉该点以及和该点相连接的边，原有的连通图，变成多个连通图。

边连通分量，是边连通度大于1的极大连通子图。其对应于桥，即去掉该边后，原有的连通图，变成多个连通图。

 

在一个大于2个顶点的图中，如果有桥的话一定有割点，但是又割点不一定有桥。

 

在POJ中3352和3177是求桥和点连通分量。

POJ 1144,1523,2117,是求割点以及每个割点能够划分几个连通分量。



对这个图，求割点，点连通分量(块),割边，边连通分量（缩点）

代码如下：


// include file
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <ctime>
 
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <bitset>
 
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <list>
#include <functional>
 
using namespace std;
 
// typedef
typedef long long LL;
typedef unsigned long long ULL;
typedef __int64 Bint;
 
//
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
#define FORi(a,b,c) for(int i=(a);i<(b);i+=c)
#define FORj(a,b,c) for(int j=(a);j<(b);j+=c)
#define FORk(a,b,c) for(int k=(a);k<(b);k+=c)
#define FORp(a,b,c) for(int p=(a);p<(b);p+=c)
#define FORii(a,b,c) for(int ii=(a);ii<(b);ii+=c)
#define FORjj(a,b,c) for(int jj=(a);jj<(b);jj+=c)
#define FORkk(a,b,c) for(int kk=(a);kk<(b);kk+=c)
 
#define FF(i,a)    for(int i=0;i<(a);i++)
#define FFD(i,a)   for(int i=(a)-1;i>=0;i--)
 
#define Z(a) (a<<1)
#define Y(a) (a>>1)
 
const double eps = 1e-6;
const double INFf = 1e10;
const int INFi = 1000000000;
const double Pi = acos(-1.0);
 
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T TMAX(T x,T y)
{
    if(x>y) return x;
    return y;
}
template<class T> inline T TMIN(T x,T y)
{
    if(x<y) return x;
    return y;
}
template<class T> inline void SWAP(T &x,T &y)
{
    T t = x;
    x = y;
    y = t;
}
template<class T> inline T MMAX(T x,T y,T z)
{
    return TMAX(TMAX(x,y),z);
}
 
// code begin
#define MAXN 100
#define MAXM 10000
int N,M;
struct node1
{
    int e;
    int next;
};
struct node2
{
    int next;
};
node1 mem[MAXM];
node2 G[MAXN];
 
int dfn[MAXN];
int low[MAXN];
int used[MAXN];
int cnt;     // 搜索编号
int cc;      // 无向图连通分量的个数
 
// 记录割点
int cut[MAXN];               //标记哪些点是割点，并且记录下，每个割点可以分割成几个分量
int cutstk[MAXN],cuttop;      // 记录下这些割点
 
// 记录块
int blockstk[MAXN],blocktop;   //辅助栈
int block[MAXN][MAXN];
int blocksize[MAXN];
int blockid;                  // 块的编号，从1开始
 
// 记录割边
struct node3
{
    node3(){};
    node3(int a,int b)
    {
        s=a;
        e=b;
    }
    int s;
    int e;
};
node3 bridge[MAXM];
int bridgetop;
 
// 记录边连通分量,其实还是记录一组点
int bbockstk[MAXN],bbocktop; //辅助栈
int bbock[MAXN][MAXN];  //
int bbocksize[MAXN];
int bbockid;            //边连通分量的编号
int bbockflag[MAXN];    //此时每个点都属于一个连通分量，所以可以给每天进行编号。
 
void Add_edge(int dx,int a,int b)
{
    mem[dx].e = b;
    mem[dx].next = G[a].next;
    G[a].next = dx;
}
 
void BCC_tarjan(int i,int fa)
{
    dfn[i] = cnt;
    low[i] = cnt;
    cnt++;
    used[i] = true;
    int son = 0;
    int dx = G[i].next;
 
    // 块的栈
    blockstk[blocktop++] = i;
 
    // 边连通分量的辅助栈
    bbockstk[bbocktop++] = i;
    while(dx!=-1)
    {
        int v = mem[dx].e;
        if(!used[v])
        {
            BCC_tarjan(v,i);
            low[i] = TMIN(low[i],low[v]);
 
            // 此处用来求割点
            if(fa==-1) son++;
            else if(low[v]>=dfn[i])
            {
                cut[i]++;
            }
 
            // 此处用来记录块
            if(low[v]>=dfn[i])
            {
                int tp;
                do
                {
                    tp = blockstk[--blocktop];
                    block[blockid][blocksize[blockid]++] = tp;
                }while(blockstk[blocktop-1]!=i);
                block[blockid][blocksize[blockid]++] = i;
                blockid++;
            }
 
            // 此处用来记录割边
            if(low[v]>dfn[i])
            {
                bridge[bridgetop++] = node3(i,v);
            }
 
            // 此处用来记录边连通分量
            if(low[v]>dfn[i])
            {
                int tp;
                while(bbockstk[bbocktop-1]!=i)
                {
                    tp = bbockstk[bbocktop-1];
                    bbockflag[tp] = bbockid;
                    bbock[bbockid][bbocksize[bbockid]++] = tp;
                    bbocktop--;
                }
                bbockid ++;
            }
        }
        else if(v!=fa)
        {
            low[i] = TMIN(low[i],dfn[v]);
        }
        dx = mem[dx].next;
    }
    // 对根判断是否割点
    if(fa==-1&&son>1) cut[i] += son-1;
 
    // 如果根是割点，块
    if(fa==-1&&son>1)
    {
        int tp;
        do
        {
            tp = blockstk[--blocktop];
            block[blockid][blocksize[blockid]++] = tp;
        }while(blockstk[blocktop-1]!=i);
        block[blockid][blocksize[blockid]++] = i;
        blockid++;
    }
 
    // 边连通分量
    if(fa==-1)
    {
        while(bbocktop>0)
        {
            bbock[bbockid][bbocksize[bbockid]++] = bbockstk[bbocktop-1];
            bbockflag[ bbockstk[bbocktop-1] ] = bbockid;
            bbocktop--;
        }
        bbockid++;
    }
}
 
int main()
{
    read;
    write;
    int a,b,dx;
    while(scanf("%d %d",&N,&M)!=-1)
    {
        if(N+M==0) break;
        FORi(1,N+1,1)
        {
            G[i].next = -1;
        }
        dx = 0;
        FORi(0,M,1)
        {
            scanf("%d %d",&a,&b);
            Add_edge(dx++,a,b);
            Add_edge(dx++,b,a);
        }
 
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(used,0,sizeof(used));
        cnt = 1;
        cc = 0;
 
        // 记录割点用的
        cuttop = 0; 
 
        // 记录块用的
        blocktop = 0;
        blockid = 1;
        memset(blocksize,0,sizeof(blocksize));
 
        // 记录割边用的
        bridgetop = 0;
 
        // 记录边连通分量用的
        bbocktop = 0;
        bbockid = 1;
        memset(bbocksize,0,sizeof(bbocksize));
        memset(bbockflag,0,sizeof(bbockflag));
 
        FORi(1,N+1,1)
        {
            if(!used[i])
            {
                cc++;
                BCC_tarjan(i,-1);
            }
        }
 
        // 一次dfs
 
        // 找出割点了
        printf("以下是割点:\n");
        FORi(1,N+1,1)
        {
            if(cut[i])
            {
                printf("%d ",i);
            }
        }
        printf("\n");
 
        // 一下是给点编的块的号
        printf("\n");
        printf("有%d个块\n以下是求块，即点连通分量\n",blockid-1);
        FORi(1,blockid,1)
        {
            printf("第%d块\n",i);
            FORj(0,blocksize[i],1)
            {
                printf("%d ",block[i][j]);
            }
            printf("\n");
        }
        printf("\n");
 
        // 求割边
        printf("\n有%d条割边\n以下是求割边:\n",bridgetop);
        FORi(0,bridgetop,1)
        {
            printf("割边%d:(%d %d)\n",i,bridge[i].s,bridge[i].e);
        }
 
        // 求边连通分量
        printf("\n有%d个边连通分量:\n",bbockid-1);
        FORi(1,bbockid,1)
        {
            printf("第%d个边连通分量\n",i);
            FORj(0,bbocksize[i],1)
            {
                printf("%d ",bbock[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

输入数据:
7 8

1 2

1 4

3 2

3 4

4 5

5 6

5 7

6 7

0 0

输出数据：
以下是割点:

4 5 

 

有3个块

以下是求块，即点连通分量

第1块

6 7 5

第2块

5 4

第3块

2 3 4 1 

 

有1条割边

以下是求割边:

割边0:(4 5)

 

有2个边连通分量:

第1个边连通分量

6 7 5

第2个边连通分量

2 3 4 1