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 |