103972024-04-01 19:14:25Valaki2Kritikus munkákcpp17Accepted 100/10093ms37544 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();
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms6636 KiB
2Accepted65ms17044 KiB
subtask225/25
3Accepted4ms8828 KiB
4Accepted4ms9060 KiB
5Accepted6ms9508 KiB
6Accepted4ms9640 KiB
7Accepted6ms9916 KiB
subtask325/25
8Accepted18ms12448 KiB
9Accepted9ms11656 KiB
10Accepted10ms11936 KiB
11Accepted14ms12692 KiB
12Accepted14ms13268 KiB
subtask425/25
13Accepted52ms23532 KiB
14Accepted48ms23556 KiB
15Accepted46ms25312 KiB
16Accepted46ms26624 KiB
17Accepted46ms27716 KiB
subtask525/25
18Accepted92ms35596 KiB
19Accepted93ms35844 KiB
20Accepted93ms36164 KiB
21Accepted90ms36840 KiB
22Accepted89ms37544 KiB