92p#11RE求调
查看原帖
92p#11RE求调
267125
宋小陀螺楼主2023/12/16 21:23
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005],dfn[10005],low[10005],ans[10005],anss,cnt;
bool stk[10005];
vector<int> gra[10005],scc[10005];
stack<int> s; 
void tarjan(int k,int lst) 
{
	int son = 0;
	dfn[k] = low[k] = ++cnt; s.push(k);
	for (auto v : gra[k]) 
	{
		if (!dfn[v]) 
		{
			son++;
			tarjan(v,k);
			if (lst != -1 && low[v] >= dfn[k] && lst != -2) 
			{
				ans[++anss] = k;
				lst = -2;
			}
			low[k] = min(low[k],low[v]);
		}
		else if (v != lst) low[k] = min(low[k],dfn[v]);
	}
	if (lst == -1 && son > 1) ans[++anss] = k;
	if (dfn[k] == low[k]) 
	{
		while (s.top() != k) s.pop();
		s.pop();
	}
}
int main()
{
	int u,v;
	cin >> n >> m;
	for (int i = 1;i <= m;i++) 
	{
		cin >> u >> v;
		gra[u].push_back(v);
		gra[v].push_back(u);
	}
	for (int i = 1;i <= n;i++) 
		if (!dfn[i]) tarjan(i,-1);
	sort(ans + 1,ans + 1 + anss);
	cout << anss << endl;
	for (int i = 1;i <= anss;i++) cout << ans[i] << ' ';
	return 0;
}
2023/12/16 21:23
加载中...