浅谈Tarjan

干啥的

Tarjan是用来求强连通分量的算法

有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。

是不是看不懂？举个栗子

graph (1)

这个图中的强连通分量有${0,1,2},{4},{3}$。

tarjan算法的过程大概就是DFS，上代码！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void tarjan(int x){//
    low[x]=dfn[x]=++depth;
    vis[x]=1;
    q.push(x);
    Graph(i,x)
        if(!dfn[e[i].v])tarjan(e[i].v),low[x]=min(low[x],low[e[i].v]);
        else if(vis[e[i].v])low[x]=min(low[x],low[e[i].v]);
    if(dfn[x]==low[x])
        while(y=q.top()){//缩点main(找到了强连通分量，加入一个点中)
        	q.pop();
        	sd[y]=x;
        	vis[y]=0;
        	if(x==y)break;
        	a[x]+=a[y];
    	}
}