https://www.luogu.org/problem/show?pid=3388
题目背景
割点
题目描述
给出一个n个点，m条边的无向图，求图的割点。
输入输出格式
输入格式：
第一行输入n,m
下面m行每行输入x,y表示x到y有一条边
输出格式：
第一行输出割点个数
第二行按照节点编号从小到大输出节点，用空格隔开
输入输出样例
输入样例#1：
6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6
输出样例#1：
1 5
说明
n,m均为100000
tarjan 图不一定联通！！！
1 #include <cstdio> 2 3 const int N(100000+5); 4 int ans,head[N],sumedge=1; 5 struct Edge 6 { 7 int v,next; 8 Edge(int v=0,int next=0):v(v),next(next){} 9 }edge[N<<1]; 10 inline void ins(int u,int v) 11 { 12 edge[++sumedge]=Edge(v,head[u]); 13 head[u]=sumedge; 14 edge[++sumedge]=Edge(u,head[v]); 15 head[v]=sumedge; 16 } 17 18 #define min(a,b) (a<b?a:b) 19 int tim,dfn[N],low[N],cutpoint[N]; 20 void Tarjan(int u,int pre) 21 { 22 int sumtredge=0,if_point=0; 23 dfn[u]=low[u]=++tim; 24 for(int v,i=head[u];i;i=edge[i].next) 25 { 26 v=edge[i].v; 27 if((pre^1)==i) continue; 28 if(!dfn[v]) 29 { 30 sumtredge++; 31 Tarjan(v,i); 32 if(low[v]>=dfn[u]) if_point=1; 33 low[u]=min(low[u],low[v]); 34 } 35 else low[u]=min(low[u],dfn[v]); 36 } 37 if(!pre) 38 { 39 if(sumtredge>1) ans++,cutpoint[u]=1; 40 } 41 else if(if_point) ans++,cutpoint[u]=1; 42 } 43 44 int main() 45 { 46 int n,m; scanf("%d%d",&n,&m); 47 for(int u,v;m--;ins(u,v)) 48 scanf("%d%d",&u,&v); 49 for(int i=1;i<=n;i++) 50 if(!dfn[i]) Tarjan(i,0); 51 printf("%d ",ans); 52 for(int i=1;i<=n;i++) 53 if(cutpoint[i]) printf("%d ",i); 54 return 0; 55 }