哪位大大帮一下忙,看看哪错了
查看原帖
哪位大大帮一下忙,看看哪错了
376424
beside_the_pavilion楼主2022/1/19 16:33

题目是这个

#include <bits/stdc++.h>

using namespace std;

const int N=2e4+10,M=2e5+10;
int n,m,h[N],e[M],nxt[M],tot;
int dfn[N],low[N],cnt,ans;
bool iscut[N];

void add(int u,int v)
{
	e[tot]=v,nxt[tot]=h[u],h[u]=tot++;
}

void tarjan(int u,int root)
{
	dfn[u]=low[u]=++cnt;
	int child=0;
	for(int i=h[u] ;~i ;i=nxt[i] )
	{
		int v=e[i];
		if(!dfn[v])
		{
			if(u==root) child++;
			tarjan(v,root);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=root) iscut[u]=true;
			else low[u]=min(low[u],dfn[v]);
		}
		if(u==root&&child>=2) iscut[u]=true;
	}
}

int main()
{
	cin >> n >> m;
	memset(h,-1,sizeof(h));
	while(m--)
	{
		int u,v; cin >> u >> v;
		add(u,v),add(v,u);
	}
	for(int i=1 ;i<=n ;i++ )
		if(!dfn[i]) tarjan(i,i);
	for(int i=1 ;i<=n ;i++ )
		if(iscut[i]) ans++;
	
	cout << ans << endl;
	
	for(int i=1 ;i<=n ;i++ )
		if(iscut[i]) cout << i << ' ';
	
	return 0;
}
2022/1/19 16:33
加载中...