图的连通之缩点2

#tarjan算法

时间戳：用一个计数变量表示时间，一个数组记录到达该点时的时间，每访问到一个新的点**时间戳+1**；

tarjan算法的核心思想是：如果当前点是我们访问到的一个连通分量中的第一个点，那么之后的点一定访问不到该点之前的时间戳，而且该点之后处于同一连通分量中的点能访问到的最小时间戳就是该点的时间戳。

![](http://imglf0.ph.126.net/j_oiotCRqFD3WCIxTus4QA==/6598173676390595289.jpg)

如上图所示（有点丑），红色为该点的时间戳，蓝色为其他图中的边，绿色为该点能到达的最小时间戳。

计算方程：最小时间戳（u）=min(u的时间戳，所有u能到达的点v中的 最小时间戳（v）{v没有分配到某个联通分量 } )；

实现：用lowbit记录某点能访问到的最早时间，time记录该点的时间戳。

每到达一个点把该点压入栈，标记vis。

如果lowbit==time则该点就是这个连通分量中的第一个点，而其他点一定能访问到他。所以一直pop直到该点被弹出。（弹出来的都属于这个连通分量）

如果不懂可以自己画个图手动模拟一下感受感受。

**如下情况 2 -> 1 ,从1开始DFS一次，2开始DFS一次，一定要区分这两次，mint不要混了！**

还有！**DFS链**必须是**自己的DFS链**

```c
int sta[N],top,ltcnt,size[N],mint[N],tcnt,belong[N];

void DFS(int u){
    int now=++tcnt;mint[u]=now;sta[++top]=u;
    for(int i=head[u];i;i=e[i].next){
        if(belong[e[i].t]!=0) continue;
        if(mint[e[i].t]==0) DFS(e[i].t);
        mint[u]=min(mint[u],mint[e[i].t]);
    }
    if(mint[u]==now){
    ltcnt++;
    
    while(sta[top]!=u) size[ltcnt]++,belong[sta[top--]]=ltcnt;
    size[ltcnt]++,belong[sta[top--]]=ltcnt;
    }
}
```

wuvin

导航

最近发表

友情链接