首页 > 代码库 > 图的联通-割点和桥
图的联通-割点和桥
求割点
DFS搜索树：用DFS对图进行遍历时，按照遍历次序的不同，我们可以得到一棵DFS搜索树。
树边：（称为父子边），可理解为在DFS过程中访问未访问节点时所经过的边。
回边：（返祖边、后向边），可理解为在DFS过程中遇到已访问节点时所经过的边。
该算法是R.Tarjan发明的。观察DFS搜索树，我们可以发现有两类节点可以成为割点：
- 对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；
- 对非叶子节点u（非根节点），若其有一子树的节点均没有指向u的祖先节点的回边，说明删除u之后，根结点与u的子树的节点不再连通；则节点u为割点。
http://cogs.pro/cogs/problem/problem.php?pid=8
#include<cstdio>#include<algorithm>using namespace std;struct Edge{ int to,next;}edge[10005];int fi[105],top,low[105],fa[105],dfn[105],kid[105];bool vis[105],cut[105];void add_edge(int from,int to){ edge[++top].next=fi[from],fi[from]=top,edge[top].to=to; edge[++top].next=fi[to],fi[to]=top,edge[top].to=from;}void dfs(int x){ //记录dfs遍历次序 static int counter = 0; dfn[x]=low[x]=++counter; vis[x]=1; if(x==4) x=4; for(int to = fi[x];to;to=edge[to].next){ int v=edge[to].to; if(!vis[v]){//节点v未被访问，则(u,v)为树边 fa[v]=x;kid[x]++; dfs(v); low[x]=min(low[x],low[v]); if(low[v]>=dfn[x])cut[x]=1; } else if(v!=fa[x]){//节点v已访问，则(u,v)为回边 low[x]=min(low[x],dfn[v]); } }}int main(){ freopen("gd.in","r",stdin); freopen("gd.out","w",stdout); int n,a,b,ans=0;scanf("%d",&n); while(~scanf("%d%d",&a,&b))add_edge(a,b); dfs(1); if(kid[1]<2)cut[1]=0; for(int i=1;i<=n;i++){ if(cut[i])ans++; } printf("%d\n",ans); for(int i=1;i<=n;i++){ if(cut[i])printf("%d\n",i); } return 0;}
求桥
对于一条边（u，v)，u为祖先，如果v的所有子树都没有指向比v先遍历到的点则（u,v）为桥
图的联通-割点和桥
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。