10397 | 2024-04-01 19:14:25 | Valaki2 | Kritikus munkák | cpp17 | Accepted 100/100 | 93ms | 37544 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 1e5;
int n, m;
vector<int> graph[1 + maxn + 1];
int indeg[1 + maxn];
int outdeg[1 + maxn];
bool vis[1 + maxn + 1];
int d[1 + maxn + 1];
int l[1 + maxn + 1];
bool cut[1 + maxn + 1];
int t;
void dfs(int cur, int par) {
t++;
d[cur] = t;
l[cur] = d[cur];
vis[cur] = true;
bool is_cut = false;
for(int nei : graph[cur]) {
if(nei == par) {
continue;
}
if(vis[nei]) {
l[cur] = min(l[cur], d[nei]);
} else {
dfs(nei, cur);
if(l[nei] >= d[cur]) {
is_cut = true;
}
l[cur] = min(l[cur], l[nei]);
}
}
if(cur != 0) {
if(is_cut) {
cut[cur] = true;
}
}
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
indeg[b]++;
outdeg[a]++;
graph[a].pb(b);
graph[b].pb(a);
}
for(int i = 1; i <= n; i++) {
if(indeg[i] == 0) {
graph[0].pb(i);
graph[i].pb(0);
}
if(outdeg[i] == 0) {
graph[n + 1].pb(i);
graph[i].pb(n + 1);
}
}
n++;
dfs(0, -1);
vector<int> ans;
for(int i = 1; i <= n - 1; i++) {
if(cut[i]) {
ans.pb(i);
}
}
cout << ans.size() << "\n";
for(int x : ans) {
cout << x << " ";
}
cout << "\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 4ms | 6636 KiB | ||||
2 | Accepted | 65ms | 17044 KiB | ||||
subtask2 | 25/25 | ||||||
3 | Accepted | 4ms | 8828 KiB | ||||
4 | Accepted | 4ms | 9060 KiB | ||||
5 | Accepted | 6ms | 9508 KiB | ||||
6 | Accepted | 4ms | 9640 KiB | ||||
7 | Accepted | 6ms | 9916 KiB | ||||
subtask3 | 25/25 | ||||||
8 | Accepted | 18ms | 12448 KiB | ||||
9 | Accepted | 9ms | 11656 KiB | ||||
10 | Accepted | 10ms | 11936 KiB | ||||
11 | Accepted | 14ms | 12692 KiB | ||||
12 | Accepted | 14ms | 13268 KiB | ||||
subtask4 | 25/25 | ||||||
13 | Accepted | 52ms | 23532 KiB | ||||
14 | Accepted | 48ms | 23556 KiB | ||||
15 | Accepted | 46ms | 25312 KiB | ||||
16 | Accepted | 46ms | 26624 KiB | ||||
17 | Accepted | 46ms | 27716 KiB | ||||
subtask5 | 25/25 | ||||||
18 | Accepted | 92ms | 35596 KiB | ||||
19 | Accepted | 93ms | 35844 KiB | ||||
20 | Accepted | 93ms | 36164 KiB | ||||
21 | Accepted | 90ms | 36840 KiB | ||||
22 | Accepted | 89ms | 37544 KiB |