24分求调
查看原帖
24分求调
342494
wxh666楼主2023/4/3 14:06

记录

#include<bits/stdc++.h>
using namespace std;
typedef int lsqxx;
struct lq{
	lsqxx v,nxt;
}e[200005];
lsqxx h[20005],cnt;
void add(lsqxx u,lsqxx v)
{
	e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;
}
int n,m;
int x,y;
stack<int>q;
bool vis[20005];
int dfn[20005],low[20005];
priority_queue<int>qp;
void tarjan(int t,int fn)
{
	q.push(t);
	vis[t]=true;
	int minfn=t;
	stack<int>p;
	dfn[t]=low[t]=fn;
	for(int i=h[t];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(vis[v])
		{
			if(dfn[minfn]>dfn[v]) minfn=v; 
		}
		else
		{
			tarjan(v,fn+1);
			if(low[v]==dfn[v])
				qp.push(-v);
		}
	}
	while(q.top()!=minfn)
		p.push(q.top()),low[q.top()]=minfn,q.pop();
	while(!p.empty()) q.push(p.top()),p.pop();
	q.pop();
	vis[t]=false;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		scanf("%d%d",&x,&y),add(x,y),add(y,x);
	tarjan(1,1);
	cout<<qp.size()<<endl;
	while(!qp.empty())
		printf("%d ",-qp.top()),qp.pop();
	return 0;
}

2023/4/3 14:06
加载中...