Featured image of post 浅谈Tarjan

浅谈Tarjan

浅谈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];
    	}
}

有啥用

1.缩点

有时候在一张图上出现了环,于是很多事情变得不太方便会卡死,这时候缩点就很有必要了,你可以把一个有环的图变成有向无环图。

用上面的图举个例子吧

缩点前

graph (1)

缩点后

graph (2)

这个点6就包括了点1,2,3。

2.割点

在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。 如果某个割点集合只含有一个顶点X(也即{X}是一个割点集合),那么X称为一个割点。

就是说这个点删除后强连通块增加了,那么这个点就是割点,如图,点1即为割点

graph (3)

怎么求割点呢?

其实和之前强连通分量中的tarjan差不多了,如果这个点的dfn比low要小,说明他的子树中没有能够到达他祖先的点,他是这个双连通分量的一个割点,但要加一个特判,根节点如果有两个及以上的儿子,那么他也是割点。

例题

P3387 【模板】缩点

P3388 【模板】割点(割顶)

参考资料

Graph Editor

强连通分量

所念皆星河
Built with Hugo
主题 StackJimmy 设计