tarjan割点（备用交换机）-526互联

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

int cnt,last[2022],head[2022],next[2022];
int num,p,low[2022],dfn[2022],stack[2022];//chil根节点的子树 
bool op[2022];
int ans,n,a,b,book_1[2022],book_2[2022];

inline void add( int v1 , int v2 ) {
	++ cnt;
	last[cnt] = head[v1];
	head[v1] = cnt;
	next[cnt] = v2;
	return;
}

void tarjan( int now , int father ) { 
	int chil = 0;
	dfn[now] = low[now] = ++num;
	stack[++ p] = now;
	op[now] = true;
	for (register int i = head[now]; i != 0; i = last[i]) {
		if ( dfn[next[i]] == 0 ) {
			tarjan( next[i] , now );
			low[now] = min( low[now] , low[next[i]] );
			if ( now == father ) {//若此节点就是根节点 
				chil ++;//若为根节点找子树个数 
			}
			else {
				if( low[next[i]] >= dfn[now] ) {
				    //如果一个点不是根，并且它的儿子在不经过它的情况下无法回到它的父亲，那么它也是割点  
					book_1[now] = 1;//不能直接book[++ans]=now因为会重复 
				}
			}
		}
		else {
			if ( op[next[i]] ) {
				low[now] = min( low[now] , dfn[next[i]] ); 
			}
		}
	}
	if( now == father && chil > 1 ) {//若子树个数大于1,则此根节点为割点 
		book_1[now] = 1;
	}
	if( low[now] == dfn[now] ) {
		int temp;
		do {
			temp = stack[p];
			op[temp] = false;
			p --;
		} while ( now != temp );
	}
	return;
}

int main() {
	scanf("%d",&n);
	while (cin>>a>>b) {
		add( a , b );
		add( b , a );
	}
	for (register int i = 1; i <= n; ++i) {
		if ( dfn[i] == 0 ) {
			tarjan( i , i );
		}
	}
	for (register int i = 1; i<= n; ++i) {
		if ( book_1[i] == 1 ) {//若i是割点 
			book_2[++ ans] = i;
		}
	}
	printf("%d\n",ans);
	if ( ans == 0 ) {
		printf("%d\n",0);
	}
	else {
		for (register int i = 1; i <= ans; ++i) {
			printf("%d\n",book_2[i]);
		}
	}
	return 0; 
}