24分求助!!!
查看原帖
24分求助!!!
463210
zzzYheng楼主2021/4/2 14:53
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4*2+10;
const int MAXM=1e5*5+10;
int n,m;
int edge[MAXM][2],head[MAXN],len;
int dfn[MAXN],low[MAXN];
int vis[MAXN],col[MAXN],num[MAXN],cnt;
int cd[MAXN];
int t;
int father;
int cut[MAXN];
int add(int x,int y){
	len++;
	edge[len][0]=x;
	edge[len][1]=head[y];
	head[y]=len;
}
int tarjan(int x){
	int i,j,col=0;
	dfn[x]=low[x]=++t;
	vis[x]=1;
	for(i=head[x];i;i=edge[i][1]){
		int y=edge[i][0];
		if(!dfn[y]){
			col++;
			tarjan(y),low[x]=min(low[x],low[y]);
			if((x!=father&&dfn[x]<=low[y]))
				cut[x]=1;
		}
		else
			low[x]=min(low[x],low[y]);
	}
	if(x==father&&col>=2)
		cut[x]=1;
}
int main(){
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(y,x);
		add(x,y);
	}
	for(i=1;i<=n;i++)
		if(!dfn[i])
			father=i,tarjan(i);
	int ans=0;
	for(i=1;i<=n;i++)
		if(cut[i]==1)ans++;
	printf("%d\n",ans);
	for(i=1;i<=n;i++)
		if(cut[i]==1)printf("%d ",i);
	return 0;
}
2021/4/2 14:53
加载中...