图的割点—又谈Tarjan

以下是割点的定义：

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

如果某个割点集合只含有一个顶点X（也即{X}是一个割点集合），那么X称为一个割点。——来自百度百科

---

用Tarjan算法求割点的基本思想是：

• 如果这个点是根节点，且有两个及以上的子树，那么他是割点，因为去掉他之后他的子树相互不能到达

• 如果这个点是非根节点，则用LOW值与DFN值去维护他的状态，且如果对于边x->y，如果low[ y ]>=dfn[ x ]，则说明y是割点

  所以与用Tarjan求强连通分量时不同的是，为了判断一个点是否是根，我们需要传递两个参数到函数中

  主程序中：

for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i,i);

子程序：

int dfn[maxn],low[maxn],tmmk=0;
bool cut[maxn];
void tarjan(int x,int rt){
    dfn[x]=low[x]=++tmmk;
    int son=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=G[i].y;
        if(!dfn[y]){
            tarjan(y,rt);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x] && x!=rt)
                cut[x]=true;
            if(x==rt)son++;
        }
        low[x]=min(low[x],dfn[y]);
    }
    if(x==rt && son>1)
        cut[x]=true;
}

至此，所有cut值为true的点都是割点了