求无向连通图割点（java）-------Tarjan算法

在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex / articulation point）。

代码1 代码2

代码：

public void findArc(int u) {

//根结点

parent[root] = -1;

//标记结点的访问性

vertexMap.get(u).wasVisited =true;

//记录结点u的dfs数

dfn[u] =low[u] = ++count;

int children =0;

Link current =adjTableSV.hashArray[u].first;

    while (current !=null) {

int v = current.id;

//(u,v)为树边

        if (vertexMap.get(v).wasVisited ==false) {

children++;

//System.out.print(children);

            parent[v] = u;

//  System.out.println("v是u的子节点"+"("+v+","+u+")");

//  System.out.println(u+"的子树："+children);

            findArc(v);

low[u] =min(low[u],low[v]);

//根节点，子树数大于1，为割点

            if (parent[u] == -1 && children >1) {

cutPoints.add(u);

//  System.out.println("割点集中添加了"+u);

            }

//非根节点，子树的低位数大于父树的dfn

            if (parent[u] != -1 &&low[v] >=dfn[u]) {

cutPoints.add(u);

// System.out.println("割点集中添加了"+u);

            }

}else if (v !=parent[u]) {

low[u] =min(low[u],dfn[v]);

}

current = current.next;

}

}