10262 2024. 03. 29 19:40:17 szil Kritikus munkák cpp17 Elfogadva 100/100 103ms 31276 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 6684 KiB
2 Elfogadva 67ms 16916 KiB
subtask2 25/25
3 Elfogadva 4ms 8532 KiB
4 Elfogadva 4ms 8828 KiB
5 Elfogadva 4ms 8980 KiB
6 Elfogadva 4ms 9116 KiB
7 Elfogadva 6ms 9692 KiB
subtask3 25/25
8 Elfogadva 19ms 12436 KiB
9 Elfogadva 10ms 11240 KiB
10 Elfogadva 10ms 11688 KiB
11 Elfogadva 14ms 12636 KiB
12 Elfogadva 14ms 12476 KiB
subtask4 25/25
13 Elfogadva 54ms 21260 KiB
14 Elfogadva 50ms 20260 KiB
15 Elfogadva 50ms 20456 KiB
16 Elfogadva 50ms 21108 KiB
17 Elfogadva 48ms 21448 KiB
subtask5 25/25
18 Elfogadva 103ms 28704 KiB
19 Elfogadva 101ms 29148 KiB
20 Elfogadva 98ms 29456 KiB
21 Elfogadva 98ms 30020 KiB
22 Elfogadva 93ms 31276 KiB