269192026-04-25 11:20:31miszorimarciKritikus munkákcpp14Elfogadva 100/10097ms10292 KiB
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M; cin >> N >> M;

    vector<vector<int>> adj(N + 1);
    vector<int> in_deg(N + 1, 0);
    vector<int> out_deg(N + 1, 0);
    vector<pair<int, int>> e(M);

    for (int i = 0; i < M; ++i) {
        cin >> e[i].first >> e[i].second;
        adj[e[i].first].push_back(e[i].second);
        in_deg[e[i].second]++;
        out_deg[e[i].first]++;
    }

    vector<bool> is_root(N + 1, false);
    vector<bool> is_leaf(N + 1, false);
    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (in_deg[i] == 0) {
            is_root[i] = true;
            q.push(i);
        }
        if (out_deg[i] == 0) is_leaf[i] = true;
    }
    vector<int> pos(N + 1);
    int t = 0;
    vector<int> temp_in_deg = in_deg;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        pos[u] = ++t;
        for (int v : adj[u]) {
            if (--temp_in_deg[v] == 0) q.push(v);
        }
    }

    vector<int> diff(N + 2, 0);

    for (int i = 0; i < M; ++i) {
        int L = pos[e[i].first];
        int R = pos[e[i].second];
        if (L + 1 < R) {
            diff[L + 1]++;
            diff[R]--;
        }
    }
    int mx_pos = 0;
    for (int i = 1; i <= N; ++i) {
        if (is_root[i]) mx_pos = max(mx_pos, pos[i]);
    }
    if (mx_pos > 1) {
        diff[1]++;
        diff[mx_pos]--;
    }

    int mn_pos = N + 1;
    for (int i = 1; i <= N; ++i) {
        if (is_leaf[i]) mn_pos = min(mn_pos, pos[i]);
    }
    if (mn_pos < N) {
        diff[mn_pos + 1]++;
        diff[N + 1]--;
    }

    vector<bool> blocked(N + 1, false);
    int current_sum = 0;
    for (int p = 1; p <= N; ++p) {
        current_sum += diff[p];
        if (current_sum > 0) blocked[p] = true;
    }


    vector<int> ans;
    for (int i = 1; i <= N; ++i) {
        if (!blocked[pos[i]]) {
            ans.push_back(i);
        }
    }

    sort(ans.begin(), ans.end());

    cout << ans.size() << "\n";
    for (int i = 0; i < (int)ans.size(); ++i)cout << ans[i] << (i == (int)ans.size() - 1 ? "" : " ");
    

    

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva50ms6708 KiB
subtask225/25
3Elfogadva2ms316 KiB
4Elfogadva2ms316 KiB
5Elfogadva2ms316 KiB
6Elfogadva2ms508 KiB
7Elfogadva2ms316 KiB
subtask325/25
8Elfogadva14ms1348 KiB
9Elfogadva6ms756 KiB
10Elfogadva7ms820 KiB
11Elfogadva9ms1036 KiB
12Elfogadva9ms1100 KiB
subtask425/25
13Elfogadva37ms4476 KiB
14Elfogadva39ms5304 KiB
15Elfogadva41ms5284 KiB
16Elfogadva39ms5076 KiB
17Elfogadva37ms5176 KiB
subtask525/25
18Elfogadva85ms10292 KiB
19Elfogadva83ms10252 KiB
20Elfogadva97ms10036 KiB
21Elfogadva82ms10020 KiB
22Elfogadva72ms10036 KiB