求调
查看原帖
求调
623697
yintaocheng楼主2023/12/4 10:50
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int s=0;
	bool f=false;
	char c=getchar();
	while(!isdigit(c))
	{
		f=(c=='-');
		c=getchar();
	}
	while(isdigit(c))
	{
		s=(s<<3)+(s<<1)+c-'0';
		c=getchar();
	}
	return f?-s:s;
}
void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}
int n,m,dfn[100005],low[100005],inde=0,res=0;
bool vis[100005],flag[100005];
vector<int>edge[100005];
void dfs(int u,int father)
{
	vis[u]=true;
	low[u]=dfn[u]=++inde;
	int child=0;
	for(auto v:edge[u])
	{
		if(!vis[v])
		{
			child++;
			dfs(v,u);
			low[u]=min(low[u],dfn[v]);
			if(father!=u&&low[v]>=dfn[u]&&!flag[u])
			{
				flag[u]=true;
                res++;
			}
		}
		else if(v!=father)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(father==u&&child>=2&&!flag[u])
	{
		flag[u]=true;
		res++;
	}
}
signed main()
{
	n=read();
	m=read();
	for(int i=1,u,v;i<=m;i++)
	{
		u=read();
		v=read();
		edge[u].emplace_back(v);
		edge[v].emplace_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			inde=0;
			dfs(i,i);
		}
	}
	write(res);
	putchar('\n');
	for(int i=1;i<=n;i++)
	{
		if(flag[i])
		{
			write(i);
			putchar(' ');
		}
	}
	return 0;
}```
2023/12/4 10:50
加载中...