割点 (2-1)

对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。

换句话说，如果删除某个顶点后，导致图不再连通，那么刚才删除的顶点就是割点。

1、4、3、2、6、5

如果顶点U的所有孩子顶点可以不通过父顶点U而访问到U的祖先顶点，那么说明此时去掉顶点U不影响图的连通性，U就不是割点。相反，如果顶点U至少存在一个孩子顶点，必须通过父顶点U才能访问到U的祖先顶点，那么去掉顶点U后，顶点U的祖先顶点和孩子顶点就不连通了，说明U是一个割点。

即判断割点的方法是：对于某个顶点u，如果至少存在一个顶点v（u的儿子），使得loωυ＞＝dfnᵤ ，即不能回到祖先，那么u点为割点。

这里我们还需要考虑一个特殊情况，就是DFS的根顶点（一般情况下是编号为0/1的顶点），因为根顶点没有祖先顶点。其实根顶点是不是割点也很好判断，如果从根顶点出发，一次DFS就能访问到所有的顶点，那么根顶点就不是割点。反之，如果回溯到根顶点后，还有未访问过的顶点，需要在邻接顶点上再次进行DFS，根顶点就是割点。

求解割点，对Tarjan算法

其中st[i]为1的点为割点

void Tarjan(int u,int p){

int son=0;

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

for(auto i:g[u]){

if(!dfn[i]){

son++;

Tarjan(i,u);

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

if(p!=-1&&low[i]＞=dfn[u]){

st[u]=1;

}

}else if(i!=p){

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

}

}

if(p==-1&&son＞1)st[u]=1;

};

割边

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

即在一个无向图中删除某条边后，图不再连通，这个边就是割边。

割点与桥（割边）的关系：

1）有割点不一定有桥,有桥一定存在割点(从判定方式也可以发现)

2）桥一定是割点依附的边。

6、7、1、2、3、5、4

判断割边的方式和割点差不多：对于某个顶点u，如果有loωυ＞＝dfnᵤ ，那么u-v为桥求解割边时和是不是根节点无关

割点集和割边集都是通过Tarjan算法求得，无论通过哪个点开始都可以

void Tarjan(int u, int p) {

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

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。