103972024-04-01 19:14:25Valaki2Kritikus munkákcpp17Elfogadva 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();
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms6636 KiB
2Elfogadva65ms17044 KiB
subtask225/25
3Elfogadva4ms8828 KiB
4Elfogadva4ms9060 KiB
5Elfogadva6ms9508 KiB
6Elfogadva4ms9640 KiB
7Elfogadva6ms9916 KiB
subtask325/25
8Elfogadva18ms12448 KiB
9Elfogadva9ms11656 KiB
10Elfogadva10ms11936 KiB
11Elfogadva14ms12692 KiB
12Elfogadva14ms13268 KiB
subtask425/25
13Elfogadva52ms23532 KiB
14Elfogadva48ms23556 KiB
15Elfogadva46ms25312 KiB
16Elfogadva46ms26624 KiB
17Elfogadva46ms27716 KiB
subtask525/25
18Elfogadva92ms35596 KiB
19Elfogadva93ms35844 KiB
20Elfogadva93ms36164 KiB
21Elfogadva90ms36840 KiB
22Elfogadva89ms37544 KiB