절단 점 - tarjan 알고리즘 이 무방 향 그림 에서 의 응용 (1)

tarjan 알고리즘 은 다양한 도 론 문제 에서 광범 위 하 게 응용 되 고 있다.현재, 우 리 는 tarjan 알고리즘 이 그림 에 없 는 절 점 을 구 할 때 응용 하 는 것 에 대해 토론 합 니 다.
무방 향도 의 절단 점 은 연 결 된 무방 향도 에서 한 점 과 그 모든 연결 을 삭제 하면 무방 향도 가 더 이상 연결 되 지 않 는 다 는 것 을 가리 키 며 이 점 을 무방 향도 의 절단 점 이 라 고 부른다.분할 점 을 구하 기 위해 서 우 리 는 몇 가지 개념 을 도입 합 니 다. (1) 트 리 변: dfs 에서 지나 간 변 (2) 회 변: 즉, 비 트 리 변 (3) dfs 배열: 즉 dfs 순서 (4) low 배열: 각 점 의 서브 트 리 안의 점 은 회 변 을 통 해 도착 할 수 있 는 dfs 순서 에서 가장 작은 점 의 dfs 순서 입 니 다.
한 점 의 dfs 순 서 는 반드시 이 점 에서 변 을 거 쳐 도착 할 수 있 는 점 의 dfs 순서 보다 크다 는 것 을 알 수 있다.그러면 만약 에 우리 가 점 하 나 를 찾 으 면 그 나무 안의 모든 점 이 hui 를 통 해 dfs 순서 가 그것 보다 작은 점 에 도착 하지 못 하 게 합 니 다. 이 점 이 바로 우리 가 찾 아야 할 점 입 니 다.dfs 나무의 노드 에 대해 만약 에 특정한 노드 에 두 그루 와 그 이상 의 나무 가 있다 면 이 점도 절 점 이다.
low 를 구 할 때, 우 리 는 우선 모든 점 의 low 가 dfs 순서 와 같 음 을 기본 으로 합 니 다.됐다.
주의 (1) 제 시 된 그림 이 반드시 연결 그림 이 아니 라 우 리 는 모든 연결 블록 에 대해 절단 점 작업 을 해 야 합 니 다.(2) 할 점 개 수 를 통계 할 때 할 점 을 찾 을 때마다 카운터 에 + 1 을 직접 계산 할 수 없습니다. 우리 가 사용 하 는 할 점 알고리즘 은 일부 점 을 반복 적 으로 계산 합 니 다.
AC 코드:

#include
#include 
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
",cctp);
	for(int i=1;i<=n;i++) if(ctp[i]) printf("%d ",i);
	return 0;
}