割点
给出一个n个点，m条边的无向图，求图的割点。
第一行输入n,m
下面mm行每行输入x,y表示x到y有一条边
第一行输出割点个数
第二行按照节点编号从小到大输出节点，用空格隔开
6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6
1 5
对于全部数据，n≤20000，m≤100000
点的编号均大于0小于等于n。
tarjan图不一定联通。
有一条边(u, v)，如果v未访问过，继续DFS，DFS完之后，low[u]=min(low[u], low[v])；
如果v访问过（且u不是v的父亲），就不需要继续DFS了，一定有dfn[v]<dfn[u]，low[u]=min(low[u], dfn[v])。
#include<cstdio> #include<iostream> #include<stack> using namespace std; stack<int>q; int n,m,cnt,sum,idx; int dfn[20005],low[20005],in[20005],head[20005],ch[20005]; struct node{ int from,to,next; }edge[200005]; void add(int from,int to) { edge[++cnt].from=from; edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt; } void tarjan(int now,int fa){ int son=0; dfn[now]=low[now]=++idx; in[now]=1; q.push(now); for(int i=head[now];i;i=edge[i].next){ int to=edge[i].to; if(!dfn[to]){ son++; tarjan(to,now); low[now]=min(low[now],low[to]); if(low[to]>dfn[now]&&!ch[now]){ ch[now]=1; sum++; } } else if(to!=fa&&dfn[to]<dfn[now]){ low[now]=min(low[now],dfn[to]); } } if(now==fa&&son>=2){ ch[now]=1; sum++; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i=1;i<=n;i++){ if(!dfn[i]){ tarjan(i,i); } } printf("%d\n",sum); for(int i=1;i<=n;i++){ if(ch[i]){ printf("%d ",i); } } return 0; }
原文：https://www.cnblogs.com/hrj1/p/11154808.html