80分求助 qwq
查看原帖
80分求助 qwq
251802
Liutian1112楼主2020/11/10 11:13
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

int dfn[maxn], low[maxn], idx;
vector<int> G[maxn];
set<int> ans;

void tarjan(int u, int root, int fa)
{
	dfn[u] = low[u] = ++idx;
	int cnt = 0;
	for(int v : G[u]) {
		if(!dfn[v]) {
			tarjan(v, root, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > dfn[u])
				cnt++;
		} else if(v != fa)
			low[u] = min(low[u], low[v]);
	}
	if((u == root && cnt > 1) || (u != root && cnt)) ans.insert(u);
}

int main()
{
	IOS();
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}	
	for(int i = 1; i <= n; i++)
		if(!dfn[i]) tarjan(i, i, 0);
	cout << ans.size() << endl;
	for(int i : ans)
		cout << i << " ";
	cout << endl;
	return 0;
}
2020/11/10 11:13
加载中...