44分求助
查看原帖
44分求助
551088
FincheuwYggdrasil楼主2022/7/25 13:47
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
long long n,m,head[maxn],cnt,root;
long long low[maxn],dfn[maxn],num;
vector<long long> ge;
bool cha[100005];
struct Edge{
	long long to,next;
}e[200005];

void add(long long u,long long v)
{
	e[cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt++;
}

void tarjan(long long u,long long fa)
{
	dfn[u] = low[u] = ++num;
	long long count = 0;
	for(long long i = head[u];~i;i = e[i].next)
	{
		long long v = e[i].to;
		if(v == fa)
			continue;
		if(!dfn[v])
		{
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
			if(low[v] >= dfn[u])
			{
				count++;
				if(u != root || count > 1)
					ge.push_back(u);
			}
		}
		else
			low[u] = min(low[u],dfn[v]);
	}
}

void init()
{
	memset(head,-1,sizeof(head));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(cha,false,sizeof(cha));
	cnt = num = 0;
}

int main()
{
	cin >> n >> m;
	init();
	long long u,v;
	while(m--)
	{
		cin >> u >> v;
		add(u,v);
		add(v,u);
	}
	for(long long i = 1;i <= n;i++)
	{
		if(!dfn[i])
		{
			root = i;
			tarjan(i,0);
		}
	}
	cout << ge.size() << endl;
	for(int i = 0;i < ge.size();i++)
	{
	    if(cha[ge[i]])
	        continue;
	    cha[ge[i]] = true;
		cout << ge[i] << endl;
	}
 	return 0;
}
2022/7/25 13:47
加载中...