102622024-03-29 19:40:17szilKritikus munkákcpp17Elfogadva 100/100103ms31276 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'010;

vector<int> g[MAXN];
int din[MAXN], dout[MAXN], tin[MAXN], low[MAXN], timer = 1;
set<int> ans;

void dfs(int u, int p = -1) {
	tin[u] = low[u] = timer++;
	for (int v : g[u]) {
		if (v == p) continue;
		if (tin[v]) {
			low[u] = min(low[u], tin[v]);
		} else {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] >= tin[u] && p != -1) ans.insert(u);
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
		dout[u]++; din[v]++;
	}
	for (int i = 1; i <= n; i++) {
		if (din[i] == 0) {
			g[0].emplace_back(i);
			g[i].emplace_back(0);
		}
		if (dout[i] == 0) {
			g[i].emplace_back(n+1);
			g[n+1].emplace_back(i);
		}
	}
	dfs(0);
	cout << ans.size() << "\n";
	for (int i : ans) cout << i << " ";
	cout << "\n";

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms6684 KiB
2Elfogadva67ms16916 KiB
subtask225/25
3Elfogadva4ms8532 KiB
4Elfogadva4ms8828 KiB
5Elfogadva4ms8980 KiB
6Elfogadva4ms9116 KiB
7Elfogadva6ms9692 KiB
subtask325/25
8Elfogadva19ms12436 KiB
9Elfogadva10ms11240 KiB
10Elfogadva10ms11688 KiB
11Elfogadva14ms12636 KiB
12Elfogadva14ms12476 KiB
subtask425/25
13Elfogadva54ms21260 KiB
14Elfogadva50ms20260 KiB
15Elfogadva50ms20456 KiB
16Elfogadva50ms21108 KiB
17Elfogadva48ms21448 KiB
subtask525/25
18Elfogadva103ms28704 KiB
19Elfogadva101ms29148 KiB
20Elfogadva98ms29456 KiB
21Elfogadva98ms30020 KiB
22Elfogadva93ms31276 KiB