0分求助
查看原帖
0分求助
668869
Fire_flame楼主2022/3/4 21:12
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int MAXN=1e5+5;
int n,m;
vector<int>g[MAXN];
int dfn[MAXN],low[MAXN],cnt;
bool vis[MAXN];
void tarjan(int u,int fa){
	vis[u]=dfn[u]=++cnt;
	int son=0;
	for(int i=0;i<g[u].size();i++){
		printf("%d ",i);
		int v=g[u][i];
		if(!dfn[v]){
			tarjan(v,u);
			if(u==fa)son++;
			else if(low[v]>=dfn[u])vis[u]=true;
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(dfn[v],low[u]);
	}
	if(son>1)vis[u]=true;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])
			tarjan(i,i);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(vis[i])ans++;
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++){
		if(vis[i])printf("%d ",i);
	}
	return 0;
}
2022/3/4 21:12
加载中...