强连通分量

有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量(Strongly Connected Component, SCC)

有向图和它的转置的强连通分量相同
所有SCC构成一个DAG

强连通图

在一个强连通图中，任意两个点都通过一定路径互相连通。比如图一是一个强连通图，而图二不是。因为没有一条路使得点4到达点1、2或3。

强连通分量

在一个非强连通图中极大的强连通子图就是该图的强连通分量。比如图三中子图{1,2,3,5}是一个强连通分量，子图{4}是一个强连通分量。

Tarjan

其实，tarjan算法的基础是DFS。我们准备两个数组Low和Dfn。Low数组是一个标记数组，记录该点所在的强连通子图所在搜索子树的根节点的Dfn值（很绕嘴，往下看你就会明白），Dfn数组记录搜索到该点的时间，也就是第几个搜索这个点的。根据以下几条规则，经过搜索遍历该图（无需回溯）和对栈的操作，我们就可以得到该有向图的强连通分量。

1、数组的初始化：当首次搜索到点p时，Dfn与Low数组的值都为到该点的时间。

2、堆栈：每搜索到一个点，将它压入栈顶。

3、当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’不在栈中，p的low值为两点的low值中较小的一个。

4、当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’在栈中，p的low值为p的low值和p’的dfn值中较小的一个。

5、每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的low值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。

6、继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。

由于每个顶点只访问过一次，每条边也只访问过一次，我们就可以在O（n+m）的时间内求出有向图的强连通分量。但是，这么做的原因是什么呢？

Tarjan算法的操作原理

1、Tarjan算法基于定理：在任何深度优先搜索中，同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说，强连通分量一定是有向图的某个深搜树子树。

2、可以证明，当一个点既是强连通子图Ⅰ中的点，又是强连通子图Ⅱ中的点，则它是强连通子图Ⅰ∪Ⅱ中的点。

3、这样，我们用low值记录该点所在强连通子图对应的搜索子树的根节点的Dfn值。注意，该子树中的元素在栈中一定是相邻的，且根节点在栈中一定位于所有子树元素的最下方。

4、强连通分量是由若干个环组成的。所以，当有环形成时（也就是搜索的下一个点已在栈中），我们将这一条路径的low值统一，即这条路径上的点属于同一个强连通分量。

5、如果遍历完整个搜索树后某个点的dfn值等于low值，则它是该搜索子树的根。这时，它以上（包括它自己）一直到栈顶的所有元素组成一个强连通分量。

模板

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
using namespace std;

const int N=1001;
int time=1;
int low[N],dfn[N];
bool instack[N];
stack<int>st;

struct LIST
{
    int v;
    LIST *next;
};
LIST *head[N]={NULL};

void tarjan(int v)/*tarjan求强连通分支*/
{
    dfn[v]=low[v]=time++;/*标记点v的DFS遍历序号*/
    st.push(v);/*将点v入栈*/
    instack[v]=true;/*标记点v已经在栈中*/
    for(LIST *p=head[v];p!=NULL;p=p->next)/*遍历V能直接到达的点*/
    {
        if(!dfn[p->v])/*如果v的邻接点没有入过栈*/
        {
            tarjan(p->v);
            low[v]=min(low[v],low[p->v]);/*如果v能直接到达的这个点没在栈中,v的最早祖先为他们中的较小值*/
        }
        else if(instack[p->v])/*如果在栈中*/
            low[v]=min(low[v],dfn[p->v]);/*如果在栈中，则v的最早祖先是他的序号和那个点的序号较小的*/
    }
    if(dfn[v]==low[v])/*如果dfn[v]和low[v]相等，则说明v点是其所属强连通分支DFS遍历起点，这个强连通分支所有点都在v点之上*/
    {
        cout<<"{ ";
        do
        {
            v=st.top();
            st.pop();
            instack[v]=false;
            cout<<v<<' ';
        }while(dfn[v]!=low[v]);
        cout<<"}"<<endl;        
    }
}

int main()
{
    int i,j,n,m;
    cin>>n;
    while(!st.empty())
        st.pop();
    memset(dfn,0,sizeof(dfn));
    memset(instack,false,sizeof(instack));
    for(i=0;i<=n;i++)
        head[i]=NULL;
    for(i=1;i<=n;i++)
    {            
        cin>>m;//i的邻接点数量
        //输入每个邻接点编号
        LIST *rear=head[i];
        for(j=0;j<m;j++)/*创建邻接表*/
        {
            if(!j)
            {
                rear=new LIST;
                head[i]=rear;
            }
            else
            {
                rear->next=new LIST;
                rear=rear->next;
            }
            rear->next=NULL;
            cin>>rear->v;
        }
    }
    for(i=1;i<=n;i++)
        if(!dfn[i])/*如果i没有入过栈*/
            tarjan(i);
    return 0;
}