tarjan算法在各种各样的图论问题中有着广泛的应用。现在，我们讨论tarjan算法在求无向图的割点时的应用。
无向图的割点，指在一张连通的无向图中，若删去一个点及其所有连边，该无向图就不再联通，则这个点被称为这张无向图的割点。为了求割点，我们引入几个概念： (1)树边：指在dfs时被经过的边 (2)回边：即非树边 (3)dfs数组：即dfs序 (4)low数组：每个点的子树内的点通过回边能到达的dfs序最小的点的dfs序
可以发现，一个点的dfs序一定比能从这个点经回边到达的点的dfs序大。那么，如果我们找到一个点，使得它的子树内的所有点都不能hui通过回边到达dfs序比它小的点，这个点就是我们要找的割点。对于dfs树上的节点，若某个节点有两棵及以上子树，那么这个点也是割点。
在求low时，我们首先默认每个点的low都与dfs序相等（这时没有搜索到任意一条回边），当搜索到回边时，就将其终点的dfs序与当前点的low比较并取最小值（即“通过回边到达的dfs序最小的点”），递归求解（每搜索完以可子树，就尝试用子树内的low更新根节点的low）即可。
注意 (1)给出的图不一定是连通图，我们应该对每个连通块进行求割点操作。 (2)在统计割点个数时，不能在每次找到割点后直接向计数器内+1，我们使用的求割点算法会重复计算某些点。
AC代码：
#include<cstdio> #include<algorithm> const int ma=1e5+5; using namespace std; int n,m,head[ma],ecnt=1;//邻接表 int x,y,f[ma]; int ctp[ma],cctp,dfn[ma],low[ma],dfsn=0;//ctp:割点 cctp:割点个数 struct list{ int r,n; }l[200020]; void add(int a,int b) { l[ecnt].r=b; l[ecnt].n=head[a]; head[a]=ecnt++; } void dfs(int x) { int c=0; low[x]=dfn[x]=++dfsn; for(int i=head[x];i;i=l[i].n) { if(!dfn[l[i].r]) { c++; f[l[i].r]=x; dfs(l[i].r); if(f[x]==0&&c>=2) ctp[x]=1; low[x]=min(low[x],low[l[i].r]); if(f[x]!=0&&dfn[x]<=low[l[i].r]) ctp[x]=1; } else if(f[x]!=l[i].r) low[x]=min(low[x],dfn[l[i].r]); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i); for(int i=1;i<=n;i++) if(ctp[i]) cctp++; printf("%d\n",cctp); for(int i=1;i<=n;i++) if(ctp[i]) printf("%d ",i); return 0; }