割顶：表示无向图中的点，这个点删除之后，原图不在联通，这样的点就是割顶。 怎么求一个图中的割顶呢？ 把无向图变成一颗树，dfs时候搜索到在dfs树上的称为树边，搜索是出现后代指向祖先的边称为反向边。 对于根节点，当他存在两个或两个以上的子节点时，那么他就是割顶。 而对于其他节点u，当且仅当u存在一个子节点v，使得v及其所有的后代都没有反向边连回u的祖先时，u是一个割顶。 那么判断就很简单，，这里给出两个模板： 题目：poj1523 和 1144都是裸的求割顶的题目 通用模板：
;const int N=1100;int dfn[N],low[N],vis[N],cnt[N];///dfn 表示深搜的时候的标号 low表示他能连到最早的点bool cut[N];int k,n,root;vector<int> g[N];void addedge(int x,int y){g[x].push_back(y);g[y].push_back(x);}void Tarjan(int u,int fa){int son = 0;vis[u] = 1;dfn[u] = low[u] = ++k;for(int i=0;i<g[u].size();i++){int v = g[u][i];if(vis[v]==1 && v!=fa)low[u] = min(low[u],dfn[v]);if(vis[v]==0){Tarjan(v,u);son++;low[u] = min(low[u],low[v]);if((u==root && son>1) || ( u!=root && low[v]>=dfn[u] ) )cut[u]= 1,cnt[u]++;}}vis[u] = 2;}int main(){// freopen(“Input.txt”,”r”,stdin);int cas = 1;while(true){int x,y,n = 0;scanf(“%d”,&x);if(x==0)break;scanf(“%d”,&y);addedge(x,y);n = max(n,x),n = max(n,y);while(~scanf(“%d”,&x) && x){scanf(“%d”,&y);n = max(n,x);n = max(n,y);addedge(x,y);}k = 0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(vis,0,sizeof(vis));memset(cut,0,sizeof(cut));memset(cnt,0,sizeof(cnt));root = 1;cnt[root] = 0; ///注意初始点会多算一次，因为它本身会把它的子节点都计算出来Tarjan(root,-1);int ans = 0;for(int i=1;i<=n;i++)if(cut[i])ans++;printf(“Network #%d\n”,cas++);if(ans==0)puts(” No SPF nodes”);else{for(int i=1;i<=n;i++){if(cut[i])printf(” SPF node %d leaves %d subnets\n”,i,cnt[i]+1);}}puts(“”);for(int i=0;i<=n;i++)g[i].clear();}return 0;}
还有一个大白书上的模板，写法差不多，但是提交到1144上wa了
;N = 1100;const int inf = 0x3f3f3f3f;vector<int> v[N];int dfs_clock;int pre[N],cnt[N];bool iscut[N];int dfs(int now,int fa){int lownow = pre[now] = ++dfs_clock;int child = 0;for(int i=0;i<v[now].size();i++){int to = v[now][i];if(pre[to]==0){child++;int lowto = dfs(to,now);lownow = min(lowto,lownow);if(lowto >= pre[now]) ///here isn’t equer?{iscut[now] = true;cnt[now]++;}}else if(pre[to] < pre[now] && to!=fa) ///erevy updatelownow = min(lownow,pre[to]);}if(fa<0 && child==1)iscut[now] = false;///low[u] = lownow; if wantreturn lownow;}int main(){// freopen(“Input.txt”,”r”,stdin);int cas = 1;while(true){int x,y,n = 0;scanf(“%d”,&x);if(x==0)break;scanf(“%d”,&y);v[x].push_back(y);v[y].push_back(x);n = max(n,x),n = max(n,y);while(~scanf(“%d”,&x) && x){scanf(“%d”,&y);n = max(n,x);n = max(n,y);v[x].push_back(y);v[y].push_back(x);}dfs_clock = 0;for(int i=0;i<=n;i++){pre[i] = 0;cnt[i] = 1;iscut[i] = false;}cnt[1] = 0; ///注意初始点会多算一次，因为它本身会把它的子节点都计算出来dfs(1,-1);int ans = 0;for(int i=1;i<=n;i++)if(iscut[i])ans++;printf(“Network #%d\n”,cas++);if(ans==0)puts(” No SPF nodes”);else{for(int i=1;i<=n;i++){if(iscut[i])printf(” SPF node %d leaves %d subnets\n”,i,cnt[i]);}}puts(“”);for(int i=0;i<=n;i++)v[i].clear();}return 0;}
海阔凭鱼跃，天高任鸟飞。我要加油，冲向我的理想。
