首页 > 代码库 > UESTC 900 方老师炸弹 --Tarjan求割点及删点后连通分量数
UESTC 900 方老师炸弹 --Tarjan求割点及删点后连通分量数
Tarjan算法。
1.若u为根，且度大于1，则为割点
2.若u不为根，如果low[v]>=dfn[u],则u为割点（出现重边时可能导致等号，要判重边）
3.若low[v]>dfn[u],则边(u,v)为桥(封死在子树内），不操作。
求割点时，枚举所有与当前点u相连的点v：
1.是重边： 忽略
2.是树边： Tarjan(v)，更新low[u]=min(low[u],low[v]); 子树个数cnt+1.如果low[v] >= dfn[u]，说明是割点，割点数+1
3.是回边： 更新low[u] = min(low[u],dfn[v])，因为此时v是u的祖先。
关于Tarjan求割点可见：http://hi.baidu.com/lydrainbowcat/item/f8a5ac223e092b52c28d591c
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#define Mod 1000000007using namespace std;#define N 10007vector<int> G[N];struct CUT{ int v,num;}cut[N];int vis[N],dfn[N],low[N],Time;int n,m,k;int cmp(CUT ka,CUT kb){ if(ka.num == kb.num) return ka.v < kb.v; return ka.num > kb.num;}void Tarjan(int u,int fa){ low[u] = dfn[u] = ++Time; int cnt = 0; vis[u] = 1; int flag = 1; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(v == fa && flag) //重边 { flag = 0; continue; } if(!vis[v]) //树边 { Tarjan(v,u); cnt++; low[u] = min(low[u],low[v]); if(low[v] >= dfn[u]) cut[u].num++; } else if(vis[v] == 1) //回边 low[u] = min(low[u],dfn[v]); } if(fa == -1 && cnt == 1) //为根且度数为1，不是割点 cut[u].num = 1; vis[u] = 2; return;}int main(){ int i,j,u,v; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { Time = 0; for(i=0;i<=n;i++) { G[i].clear(); cut[i].v = i; cut[i].num = 1; } cut[0].num = 0; //根要特判 while(m--) { scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(vis,0,sizeof(vis)); Tarjan(0,-1); sort(cut,cut+n,cmp); for(i=0;i<k;i++) printf("%d %d\n",cut[i].v,cut[i].num); printf("\n"); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。