10397 2024. 04. 01 19:14:25 Valaki2 Kritikus munkák cpp17 Elfogadva 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();
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 6636 KiB
2 Elfogadva 65ms 17044 KiB
subtask2 25/25
3 Elfogadva 4ms 8828 KiB
4 Elfogadva 4ms 9060 KiB
5 Elfogadva 6ms 9508 KiB
6 Elfogadva 4ms 9640 KiB
7 Elfogadva 6ms 9916 KiB
subtask3 25/25
8 Elfogadva 18ms 12448 KiB
9 Elfogadva 9ms 11656 KiB
10 Elfogadva 10ms 11936 KiB
11 Elfogadva 14ms 12692 KiB
12 Elfogadva 14ms 13268 KiB
subtask4 25/25
13 Elfogadva 52ms 23532 KiB
14 Elfogadva 48ms 23556 KiB
15 Elfogadva 46ms 25312 KiB
16 Elfogadva 46ms 26624 KiB
17 Elfogadva 46ms 27716 KiB
subtask5 25/25
18 Elfogadva 92ms 35596 KiB
19 Elfogadva 93ms 35844 KiB
20 Elfogadva 93ms 36164 KiB
21 Elfogadva 90ms 36840 KiB
22 Elfogadva 89ms 37544 KiB