5408 | 2023-05-13 10:28:55 | TomaSajt | Kritikus munkák | cpp17 | Wrong answer 50/100 | 93ms | 28648 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> d, l;
set<int> res;
int t = 0;
void dfs(int u) {
d[u] = l[u] = ++t;
for (auto &v : g[u]) {
if (d[v]) {
l[u] = min(l[u], d[v]);
continue;
}
dfs(v);
l[u] = min(l[u], l[v]);
if (l[v] >= d[u]) res.insert(u);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
g.resize(n + 2), d.resize(n + 2), l.resize(n + 2);
vector<int> in_deg(n + 1), out_deg(n + 1);
while (m--) {
int u, v;
cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
out_deg[u]++, in_deg[v]++;
}
for (int i = 1; i <= n; i++) {
if (in_deg[i] == 0) g[0].push_back(i), g[i].push_back(0);
if (out_deg[i] == 0) g[n + 1].push_back(i), g[i].push_back(n + 1);
}
dfs(0);
res.erase(0), res.erase(n + 1);
cout << res.size() << '\n';
for (auto &r : res) cout << r << ' ';
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1828 KiB | ||||
2 | Accepted | 57ms | 13376 KiB | ||||
subtask2 | 25/25 | ||||||
3 | Accepted | 57ms | 13376 KiB | ||||
4 | Accepted | 2ms | 2128 KiB | ||||
5 | Accepted | 3ms | 2400 KiB | ||||
6 | Accepted | 3ms | 2688 KiB | ||||
7 | Accepted | 3ms | 2684 KiB | ||||
8 | Accepted | 4ms | 3076 KiB | ||||
subtask3 | 25/25 | ||||||
9 | Accepted | 4ms | 3076 KiB | ||||
10 | Accepted | 16ms | 5664 KiB | ||||
11 | Accepted | 8ms | 4312 KiB | ||||
12 | Accepted | 8ms | 4440 KiB | ||||
13 | Accepted | 12ms | 5120 KiB | ||||
14 | Accepted | 12ms | 5052 KiB | ||||
subtask4 | 0/25 | ||||||
15 | Accepted | 12ms | 5052 KiB | ||||
16 | Accepted | 48ms | 16236 KiB | ||||
17 | Wrong answer | 46ms | 15272 KiB | ||||
18 | Wrong answer | 45ms | 15472 KiB | ||||
19 | Wrong answer | 45ms | 16180 KiB | ||||
20 | Wrong answer | 45ms | 16464 KiB | ||||
subtask5 | 0/25 | ||||||
21 | Wrong answer | 45ms | 16464 KiB | ||||
22 | Wrong answer | 89ms | 25868 KiB | ||||
23 | Wrong answer | 93ms | 26312 KiB | ||||
24 | Wrong answer | 92ms | 26364 KiB | ||||
25 | Wrong answer | 89ms | 26968 KiB | ||||
26 | Wrong answer | 86ms | 28648 KiB |