首页 > 代码库 > 【模板】割点（割顶）
【模板】割点（割顶）
题目背景
割点
题目描述
给出一个n个点，m条边的无向图，求图的割点。
输入输出格式
输入格式：第一行输入n,m
下面m行每行输入x,y表示x到y有一条边
输出格式：第一行输出割点个数
第二行按照节点编号从小到大输出节点，用空格隔开
输入输出样例
输入样例#1：
6 71 21 31 42 53 54 55 6
输出样例#1：
1 5
说明
n,m均为100000
tarjan 图不一定联通！！！
思路
dfs求割点；
在DFS搜索树，我们可以发现有两类节点可以成为割点：
- 对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；
- 对非叶子节点u（非根节点），若其子树的节点均没有指向u的祖先节点的回边，说明删除u之后，根结点与u的子树的节点不再连通；则节点u为割点。
2即n->v边中low[v]>=dfn[u];
代码实现
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=3e5; 5 inline int min_(int x,int y){return x<y?x:y;} 6 int n,m; 7 int a,b; 8 int h[maxn],hs,et[maxn],en[maxn]; 9 void add(int u,int v){10 ++hs,et[hs]=v,en[hs]=h[u],h[u]=hs;11 ++hs,et[hs]=u,en[hs]=h[v],h[v]=hs;12 }13 int s[maxn],ss;14 int dfn[maxn],dfns,low[maxn],v[maxn];15 void tarjan(int k,int f){16 dfn[k]=low[k]=++dfns;17 for(int i=h[k];i;i=en[i])18 if(et[i]!=f){19 if(dfn[et[i]]){20 low[k]=min_(low[k],dfn[et[i]]);21 }22 else{23 tarjan(et[i],k);24 low[k]=min_(low[k],low[et[i]]);25 if(low[et[i]]>=dfn[k]) ++v[k];26 }27 }28 if(f&&v[k]) s[++ss]=k;29 if(!f&&v[k]>1) s[++ss]=k;30 }31 int main(){32 scanf("%d%d",&n,&m);33 for(int i=1;i<=m;i++){34 scanf("%d%d",&a,&b);35 add(a,b);36 }37 for(int i=1;i<=n;i++){38 if(!dfn[i]){39 dfns=0;40 tarjan(i,0);41 }42 }43 sort(s+1,s+ss+1);44 printf("%d\n",ss);45 for(int i=1;i<=ss;i++) printf("%d ",s[i]);46 putchar(‘\n‘);47 return 0;48 }
感谢；
http://www.cnblogs.com/en-heng/p/4002658.html
助我一A；
【模板】割点（割顶）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。