无向图割点 - xIao_wU 思维磁场 - Just Run And Never Forget I Have A Dream

无向图割点

xIao.wU posted @ 2009年12月30日 22:04 in 图论 , 1533 阅读

建议阅读：黄劲松《无向图的块与圈》

求割点主要理解三个定理：

w定理1：DFS中，e=uv是返祖边，那么要么u是v的祖先，要么u是v的后代子孙。

w定理2：DFS中，e=uv是父子边，且dfn[u] > 1，low[v] ≥ dfn[u]，则u是割点。

w定理3：DFS的根r是割点的充要条件是：至少有2条以r为尾(从r出发)的父子边。

定理1是毋庸置疑的，定理2则是运用定理1来确定u是割点，通俗的表述则为如果 v 是 u 的儿子，而 v 的老祖先也是 u 的后代，则 u 为割点，可以想象，若 u 被去掉，v 的祖先则无法和u的祖先相连接，故u则为割点。定理2有个dfn[u] > 1，则是因为定理三，当dfn[u] == 1时，u为根节点，故需要定理三来补充说明。具体证明过程可以阅读上面的ppt。

下面是在pku 1144 network 上的具体实现， RE了一次，就是由于inp数组只开了N ，明显不足...

     #include <iostream>
using namespace std;

const int N = 104;
int mat[N][N], n , low[N] , dfn[N] , cut[N] , sign , cnt;
char inp[N * N];

void DFS(int u) {
low[u] = dfn[u] = sign ++;
for(int v=1; v <= n; v++) {
if(mat[u][v]) {
mat[v][u] = mat[u][v] = false;
if(!dfn[v]) { //u v 则为父子边
if(u == 1) cnt ++; //统计以1为根的父子边数量
DFS(v);
low[u] = min(low[u] , low[v]);
if(low[v] >= dfn[u]) cut[u] = 1;
}
else //u v 为返祖边
low[u] = min(low[u] , dfn[v]);
}
}
}

void init()
{
memset(mat , 0 , sizeof(mat));
memset(dfn , 0 , sizeof(dfn));
memset(cut , 0 , sizeof(cut));
}

int main()
{
//freopen("in.txt" , "r" , stdin);
while(scanf("%d", &n) , n) {
getchar();
init();
while(gets(inp) , inp[0] != '0') {
int root , data = 0 , Len = strlen(inp);
inp[Len] = ' ';
bool Fnode = false;
for(int i=0; i <= Len; i++) {
if(inp[i] >= '0' && inp[i] <= '9') {
data *= 10;
data += inp[i] - '0';
}
else {
if(!Fnode) {
Fnode = true;
root = data;
}
else {
mat[root][data] = 1;
mat[data][root] = 1;
}
data = 0;
}
}
}
sign = 1 ,cnt = 0;
DFS(1);
                if(cnt < 2) cut[1] = 0;
int ans = 0;
for(int i=1; i <= n; i++)
if(cut[i]) ans ++;
printf("%d\n" , ans);
}
return 0;
}