80分求调
查看原帖
80分求调
1083200
guojiahong楼主2024/8/13 14:10
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,dfn[20001],low[20001],fa[20001];
int ans[20001];
vector<int> to[20001];
bool vis[20001],tf[20001];
void tarjan(int u)
{
	cnt++;
	dfn[u]=low[u]=cnt;
	vis[u]=1;
	int len=to[u].size();
	for(int i=0;i<len;i++)
	{
		if(!vis[to[u][i]])
		{
			fa[to[u][i]]=u;
			tarjan(to[u][i]);
			low[u]=min(low[u],low[to[u][i]]);
		}
		else if(fa[u]!=to[u][i])low[u]=min(dfn[to[u][i]],low[u]);
	}
	return ;
}
int main(){
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			tarjan(i);
			tf[i]=1;
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int len=to[i].size();
		for(int j=0;j<len;j++)
		{
			if(low[to[i][j]]>dfn[i]&&(!tf[i]||to[i].size()>=2))
			{
				cnt++;
				ans[cnt]=i;
				break;
			}
		}
	}
	cout<<cnt<<'\n';
	for(int i=1;i<=cnt;i++)cout<<ans[i]<<' ';
	return 0;
}
2024/8/13 14:10
加载中...