有人帮忙看一下吗 WA80pts on #11#12
查看原帖
有人帮忙看一下吗 WA80pts on #11#12
1083200
guojiahong楼主2024/6/9 12:55
#include<bits/stdc++.h>
using namespace std;
vector<int> to[20001];
bool vis[20001];
int dfncnt,dfn[20001],low[20001],ans[20001],fa[20001];
void tarjan(int u)
{
	vis[u]=1;
	dfncnt++;
	dfn[u]=low[u]=dfncnt;
	int len=to[u].size();
	for(int i=0;i<len;i++)
	{
		int v=to[u][i];
		if(vis[v]){if(fa[u]!=v)low[u]=min(low[u],dfn[v]);}
		else
		{
			fa[v]=u;
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
	}
	return ;
}
bool p(int node)
{
	int now=0;
	int len=to[node].size();
	for(int i=0;i<len;i++)
	{
		int child=to[node][i];
		if(low[child]>dfn[node])now++;
	}
	if(now>=2||(now>=1&&fa[node]))return 1;
	else return 0;
}
int main(){
	cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		to[x].push_back(y);
		to[y].push_back(x);
	}
	for(int i=1;i<=n;i++)if(!vis[i])tarjan(i);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(p(i))
		{
			cnt++;
			ans[cnt]=i;
		}
	}
	cout<<cnt<<'\n';
	for(int i=1;i<=cnt;i++)cout<<ans[i]<<' ';
	return 0;
}
2024/6/9 12:55
加载中...