tarjan求割点

首先，我们要了解一下割点的定义：把这个点去掉之后，这个点所在的联通块就会被分成若干个联通块。

既然这样，也就是说，只要这个节点某一个子节点所到达的节点的dfsdfsdfs序大于等于该节点的dfsdfsdfs序，即它的这个子节点无法到达dfsdfsdfs序小于该节点的节点，就说明它是一个割点了。

而对于一个联通块第一个访问的节点，则需特判，如果它在遍历完一个节点所能遍历到的所有节点，还能找到没有被遍历过的节点，就说明它是一个割点。

#include<iostream>
#include<cstring>
using namespace std;
struct edge{
	int v,fail;
	edge(){
	}
	edge(int a,int c){
		v=a;
		fail=c;
	}
}e[200100];
int len,head[200100];
int num,vis[200100];
void add(int a,int b){
	e[len]=edge(b,head[a]);
	head[a]=len++;
} 
int ti,dfn[200100],low[200100];
void tarjan(int now,int fa){
	low[now]=dfn[now]=++ti;
	int cnt=0; 
	for(int i=head[now];~i;i=e[i].fail){
		if(e[i].v==fa)
		    continue;
		if(!dfn[e[i].v]){
		    cnt++;
			tarjan(e[i].v,now);
			low[now]=min(low[now],low[e[i].v]);
			if(low[e[i].v]>=dfn[now]){
				if(fa>0) 
				    vis[now]=1,num++; 
			}
		}
		else
			low[now]=min(low[now],dfn[e[i].v]);
	}
	if(fa<0&&cnt>=2) 
	vis[now]=1,num++;
} 
int main(){
	//freopen("a.in","r",stdin);
	memset(head,-1,sizeof(head));
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b;
		add(a,b);
		add(b,a); 
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i,-1);
	}
	//cout<<num<<endl;
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(vis[i])cnt++;
		//cout<<i<<" ";
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++){
		if(vis[i])cout<<i<<" ";
	} 
	cout<<endl;
	return 0; 
}