图的割点与割边学习笔记
割点
割点:如果在图G中删去一个结点u后,图G的连通分枝数增加,即W(G-u)>W(G),则称结点u为G的割点,又称关节点。
直观地说,就是删除了连通图的某点后,图不在连通,而是分为几个连通分量。
性质:(1)考虑根节点Root,如果Root有数量多于1的子结点时,Root是割点。
(2)考虑非根结点u,当且仅当u的某个儿子及儿子的子孙均没有指向u的祖先的后向边时,u是割点。(LOW[v]>=DFN[u],v是u的孩子)
代码:
void DFS(int cur,int par) { dfn[cur]=low[cur]=++Index; int size=adj[cur].size(); int cnt=0; for(int i=0;i<size;i++) { int v=adj[cur][i]; if(!dfn[v]) { cnt++; DFS(v,cur); if(low[cur]>low[v]) low[cur]=low[v]; if((cur==root&&cnt==2)||(cur!=root&&low[v]>=dfn[cur])) flag[cur]=true; } else if(v!=par&&low[cur]>dfn[v]) low[cur]=dfn[v]; } }
割边
割边:如果在图G中删去一条边e后,图G的连通分支数增加,即W(G-e)>W(G),则称边u为G的桥,又称割边或关节边。
性质: 对于一条边<u,v>,v是u的孩子如果儿子及儿子的子孙均没有指向u的祖先的后向边时,<u,v>是割边。(LOW[v]>DFN[u])
代码:
void CutEdge(int cur,int par) { dfn[cur]=low[cur]=++Index; for(int i=head[cur];i;i=buf[i].next) { int v=buf[i].v; if(v==par)continue; if(!dfn[v]) { CutEdge(v,cur); if(low[cur]>low[v]) low[cur]=low[v]; if(low[v]>dfn[cur]) { ans[nAns++]=buf[i].id; } } else if(low[cur]>dfn[v]) low[cur]=dfn[v]; } }
相关习题:
POJ 1144 Network 赤果果的求割点的题。
相关链接:
Beyond the Void的讲解,很精彩
推荐阅读:
lrj的黑书P285