首页 > 代码库 > 割点与桥

割点与桥

2024-10-15 12:32:02   214人阅读

题目描述

给定一张无向图G(V,E),你需要找出所有的割点与桥.

输入

第一行给出两个正整数V,E.

接下来E行每行两个正整数x,y，表示有一条连接x,y的边。

输出

输出共2行，第一行输出所有割点的编号，第二行输出所有桥的编号。

样例输入

7 8
1 2
1 3
1 7
2 3
3 4
3 5
4 5
5 6

样例输出

1 3 5 
3 8

提示

 

割点与桥的定义：


割点：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。


割边(桥)：删掉它之后，图必然会分裂为两个或两个以上的子图。


割点与桥分别按从小到大的顺序输出


1<=V,E<=5*10^5


保证无重边与自环

技术分享

 

 DFS搜索树：用DFS对图进行遍历时，按照遍历次序的不同，我们可以得到一棵DFS搜索树，如图(b)所示。

树边：在搜索树中的实线所示，可理解为在DFS过程中访问未访问节点时所经过的边。

回边：在搜索树中的虚线所示，可理解为在DFS过程中遇到已访问节点时所经过的边。

求割点：

该算法是R.Tarjan发明的。观察DFS搜索树，我们可以发现有两类节点可以成为割点：

1.对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；

2.对非叶子节点u（非根节点），若其子树的节点均没有指向u的祖先节点的回边，说明删除u之后，根结点与u的子树的节点不再连通；则节点u为割点。

对于根结点，显然很好处理；但是对于非叶子节点，怎么去判断有没有回边是一个值得深思的问题。

我们用dfn[u]记录节点u在DFS过程中被遍历到的次序号，low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点（即DFS次序号最小），那么low[u]的计算过程如下：

技术分享

下表给出图(a)对应的dfn与low数组值。

i0123456789101112
vertex A B C D E F G H I J K L M
dfn[i] 1 5 12 10 11 13 8 6 9 4 7 2 3
low[i] 1 1 1 5 5 1 5 5 8 2 5 1 1

对于情况2，当(u,v)为树边且low[v] >= dfn[u]时，节点u才为割点。该式子的含义：以节点v为根的子树所能追溯到最早的祖先节点要么为v要么为u。

求桥：

在割点操作的基础上，求桥只要一个判断，当low[v]==dfn[v]且（u，v）为树边时，边（u，v）才是桥。

注意：这张图有可能不连通，桥的编号只要按输入顺序建链表，找到一座桥后，把它在链表里的位置/2即可（因为边是双向的），链表下标要从2开始

#include<iostream> 
#include<cstdio> 
using namespace std; 
int n,m,dfn[500002],low[500002],t=0,tot=0;bool point[500002],a[500002],bridge[500002]; 
int ch=0,to[1000004],nxt[1000004],h[500002],k=1;
inline int read(){  
    register int x;register bool f;register char c;  
    for (f=0; (c=getchar())<‘0‘||c>‘9‘; f=c==‘-‘);  
    for (x=c-‘0‘; (c=getchar())>=‘0‘&&c<=‘9‘; x=(x<<3)+(x<<1)+c-‘0‘);  
    return f?-x:x;  
}  
inline void ins(int x,int y){to[++k]=y,nxt[k]=h[x],h[x]=k;}  
void dfs(int x,int fa) 
{ 
    dfn[x]=++t;low[x]=dfn[x];a[x]=1; 
    for(int i=h[x];i;i=nxt[i]) 
    { 
        int y=to[i];if(y==fa)continue; 
        if(!dfn[y]) 
        { 
            dfs(y,x);low[x]=min(low[x],low[y]); 
            if(low[y]>=dfn[x])point[x]=1;if(x==fa)ch++; 
            if(low[y]==dfn[y])bridge[i>>1]=1; 
        } 
        else low[x]=min(low[x],dfn[y]); 
    } 
} 
int main() 
{ 
    int n=read(),m=read(); 
    for(int i=1;i<=m;i++) 
    { 
        int u,v;u=read();v=read();
        ins(v,u);ins(u,v); 
    } 
    for(int i=1;i<=n;i++) 
    { 
        if(!a[i]) 
        { 
            ch=0;dfs(i,i);if(ch<=1)point[i]=0; 
        } 
    } 
    for(int i=1;i<=n;i++)if(point[i])printf("%d ",i);puts(""); 
    for(int i=1;i<=m;i++)if(bridge[i])printf("%d ",i); 
    return 0; 
}

 

割点与桥


联系
我们