No.8.3 图的割点与割边 - Tarjan算法
一、割点 -- 兵家必争之地：
在一个无向连通图中，如果删除某个顶点后，图不再连通，这样的顶点称为“割点”：即遍历图时寻找这样的点K，使得图被分成两部分，一部分已经访问过，一部分没有被访问过，没被访问的点集中至少有一个点在不经过K的情况下，到已经被访问过的点集距离是无穷大infinity！
1.最简单的方法是，任选一个顶点删除，然后用深度、广度优先搜索来检测图是否依然连通，世间复杂度O(N(N+M))，N=顶点数，M=边数。
2.引入树（无向连通图，且无回路）的概念，假设点K，它有子节点（x1,x2,...），如果这些节点没有其他的父节点，那么K就是割点。（问题是，如果一颗树中，某个子节点有多个父节点的话，就出现了回路，不再是树了）=》于是，对K的子节点（x1,x2,...）进行深度遍历，但是该遍历不允许经过节点K，检测是否可以完成图的遍历。
=》 如果已知下面两个数组：（关键是数组 low 如何得到？）
num[i]：为顶点 i 的时间戳(深度搜索时，被访问到的时间戳)
low[i]：顶点 i 不经过父节点时，能回到的“最小时间戳（最远的祖先）”
对任一顶点 u，num[u] 为其时间戳，其子节点 v : low[v] 表示不经过父节点 u 时，v可以回到的最远时间戳（值越大，离的越近；值越小，离的越远）；如果 low[v] >= num[u]，说明 v 走不远，无法回到祖先的时间戳，从而说明 u 是割点！
二、Code
int n,m,e[9][9],root; //root=根节点
int num[9],low[9],flag[9],index; //index=遍历顶点的时间戳(自增)
int min(int a,int b){
return a}
void dfs(int cur,int father){
int child=0,i,j;
index++;
num[cur]=index; // 初始化 num[cur], low[cur] 为当前时间戳
low[cur]=index;
for(i=1;i<=n;i++){ // a.枚举与当前顶点 cur 有边相连的顶点 i
if(e[cur][i]==1){
if(num[i]==0){ //时间戳为0，表示顶点 i 还没被访问过
child++;
dfs(i,cur); // b.深度遍历相邻的边
low[cur]=min(low[cur],low[i]); // d.返回到 i - 1 层，更新当前节点的父节点的 low[cur]
if(cur!=root && low[i]>=num[cur]) //非根节点，割点满足有子节点 low[child] >= num[father]
flag[cur]=1;
if(cur==root && child>=2) // 因为限制死了root=1，如果子节点个数多于2，它也是割点
flag[cur]=2;
}
else if(i!=father){ // c.深度遍历，如果有回路，b执行完，就会执行到此处，low[cur] = num[i]，i 一定是当前节点的父节点的。。。父节点或者祖先！
low[cur]=min(low[cur],num[i]);
}
}
}
}
int main(){
int i,j,x,y;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
e[i][j]=0;
for(i=1;i<=m;i++){
scanf("%d %d%",&x,&y);
e[x][y]=1;
e[y][x]=1;
}
root=1;
dfs(1,root);
for(i=1;i<=n;i++){
if(flag[i]==1)
printf("\nNot root: %d ",i);
if(flag[i]==2)
printf("\nRoot: %d",i);
}
getchar();getchar();
return 0;
}
上述例子中，节点1并不被认为是根节点，所以结果中只有顶点2是割点；因为深度遍历的时候，顶点1只访问了一次 1->3->2->4->2->5->6.
三、小结
1.可以自己画一个带有根节点root=1的树，测试一下；
2.if(cur==root && child>=2) flag[cur]=2; 这个判断条件，也可以试下，调整到for循环的第一层；
3.显然，上述算法时间复杂度是O(N*N)，因为用的是邻接矩阵；改为邻接表存储，时间复杂度可以优化为O(N+M)；
四、兵家必争之地，必然有重兵把守，易守难攻；但是“守”永远是被动的，主动进攻者，只需找出一处弱点，即可以点破面。现在兵力不足，先占据一条重要补给线（割边），进可攻 退可守！
上例中，割点的满足条件是，有子节点使得
low[child] >= num[father]
小于号成立时，说明子节点可以不经过父节点回到祖先节点；等于号成立时，说明子节点可以通过其他路径，最远到达父节点；如果连父节点都回不去的话，说明 low[child] > num[father]；
int index,num[9],low[9],flag[9];
int e[9][9];
int n,m;
int root=1;
int min(int a,int b){
return a < b ? a : b;
}
void dfs(int cur,int father){
int i,j;
index++;
num[cur]=index;
low[cur]=index;
for(i=1;i<=n;i++){
if(e[cur][i]==1){
if(num[i]==0){
dfs(i,cur);
low[cur]=min(low[cur],low[i]);
if(low[i]>num[cur]) //不需要判断是不是root
printf("%d - %d \t",cur,i);
}
else if(i!=father){
low[cur]=min(low[cur],num[i]);
}
}
}
}
int main(){
int i,j;
int a,b;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
e[i][j]=0;
for(i=1;i<=m;i++){
scanf("%d %d",&a,&b);
e[a][b]=1;
e[b][a]=1;
}
dfs(1,root);
getchar();getchar();return 0;
}
结果：