缩点和Tarjan求强连通分量模板（scc）

百度百科：

定义： 无向图的极大连通子图称为图的连通分量。

 任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

相关定义：

连通图：

若中任意两个不同的顶点 和 都连通（即有路径），则称为连通图。

强连通图：

在有向图G中，任意两个顶点a和b都可以互相到达，那么称该图为强连通图。

强连通分量

有向图的极大强连通子图称为该图的强连通分量，强连通图只有一个强连通分量，即是其自身。

非强连通的有向图有多个强连通分量。

上面这些百度说的都是些什么玩意？———————————————————————隔离线

缩点：

在一个有向图里面，把所有的同一个强连通分量的节点当做是一个节点

如下图所示，A，B，C，D之间都是可以两两互相到达的，则称{A,B,C,D}是一个强连通分量

 同时节点E也是一个强连通分量{E}.则下图中有两个强连通分量{E}，{A,B,C,D}

在经过缩点之后，把两个强连通分量看做是两个节点。

 Tarjan算法（寻找有向图中的强连通分量）：
相关定义：
时间戳：
在DFS遍历一个图的时候，按照次序的先后给每一个节点一个编号。

在Tarjan中需要建立两个时间戳，

一个是now[i]，表示节点i在dfs中得到的编号

一个是low[i]，表示从i开始遍历，所能走到的最小时间戳。

如果有now[i]==low[i],说明节点i是i所在的强连通分量的最高点，可以用来代表图中的某一个强连通分量。

模板：

void tarjan(int u)
{
    dfs[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[i])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }else 
        {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u])
    {
        int y;
        ++scc_cnt;
        do
        {
          y=stk[top--];
          in_stj[y]=false;
          id[y]=scc_cnt;
          id[y]=scc_cnt;  
        }while(y！=u);
    }
}

在做完tarjan求连通分量的时候，按照连通分量编号递减的顺序的已经是拓扑序，不需要再做一遍拓扑排序。在最后进行强连通分量标号的时候，因为是一个一个弹出栈的先出栈的节点一定是后出栈的节点的子树当中的节点，如果，从子节点没办法回到节点，那么当前子节点的标号就一定会比上面的点的编号要小，

缩点：

遍历所有节点的每一条边，如果两个节点不再一个连通分量里面，就加上一条从id[x]到id[y]的边。