10604 2024. 04. 06 14:24:33 Ablablabla Kritikus munkák cpp17 Elfogadva 100/100 202ms 40152 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> csucsok;

int main()
{
    int n, m;
    cin >> n >> m;

    csucsok.assign(n, vector<int>());
    vector<int> befok(n);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;

        csucsok[a].push_back(b);
        befok[b]++;
    }

    queue<int> bejar;
    vector<bool> bejart(n, 0);
    vector<vector<int>> szintek(1, vector<int>());
    vector<int> tav(n, 0);
    for(int i = 0; i < n; i++){
        if(befok[i] == 0){
            bejar.push(i);
            szintek[0].push_back(i);
        }
    }

    while(!bejar.empty()){
        int akt = bejar.front();
        bejar.pop();

        if(bejart[akt]) continue;

        bejart[akt] = 1;

        for(int x : csucsok[akt]){
            if(bejart[x]) continue;

            befok[x]--;

            if(befok[x] == 0){
                bejar.push(x);
                tav[x] = tav[akt] + 1;
                if(szintek.size() <= tav[x]){
                    szintek.push_back(vector<int>());
                }

                szintek[tav[x]].push_back(x);
            }
        }
    }

    // egyedul van a layereben
    // folotte levoknek nincs kapcsolat az alatta levokkel

    int maxi = 0;
    vector<int> jok;
    for(int i = 0; i < szintek.size(); i++){
        if(szintek[i].size() == 1 && maxi <= i){
            jok.push_back(szintek[i][0] + 1);
        }

        for(int akt : szintek[i]){
            for(int x : csucsok[akt]){
                maxi = max(maxi, tav[x]);
            }
        }
    }

    sort(jok.begin(), jok.end());
    cout << jok.size() << "\n";
    for(int x : jok){
        cout << x << " ";
    }
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1952 KiB
2 Elfogadva 123ms 13244 KiB
subtask2 25/25
3 Elfogadva 3ms 3904 KiB
4 Elfogadva 3ms 4068 KiB
5 Elfogadva 4ms 4468 KiB
6 Elfogadva 3ms 4504 KiB
7 Elfogadva 6ms 4916 KiB
subtask3 25/25
8 Elfogadva 34ms 6560 KiB
9 Elfogadva 14ms 6544 KiB
10 Elfogadva 14ms 7028 KiB
11 Elfogadva 25ms 7516 KiB
12 Elfogadva 25ms 7828 KiB
subtask4 25/25
13 Elfogadva 83ms 14056 KiB
14 Elfogadva 97ms 17700 KiB
15 Elfogadva 94ms 19876 KiB
16 Elfogadva 89ms 21104 KiB
17 Elfogadva 90ms 22232 KiB
subtask5 25/25
18 Elfogadva 199ms 31640 KiB
19 Elfogadva 194ms 35528 KiB
20 Elfogadva 202ms 37908 KiB
21 Elfogadva 186ms 38892 KiB
22 Elfogadva 178ms 40152 KiB