89352024-02-06 00:31:51kukkermanKerékpártúra (50 pont)cpp17Elfogadva 50/5063ms11076 KiB
#include <iostream>
#include <vector>

using Graf = std::vector<std::vector<int>>;

void beolvas(std::istream &be, int &k, Graf &g) {
    int n, m;
    be >> n >> m >> k;

    k--;

    g.resize(n);
    for (int i = 0; i < m; i++) {
        int honnan, hova;
        be >> honnan >> hova;
        g[honnan - 1].push_back(hova - 1);
    }
}

Graf transzponalt(const Graf &g) {
    const int n = g.size();

    Graf tg(n);
    for (int honnan = 0; honnan < n; honnan++) {
        for (auto hova: g[honnan]) {
            tg[hova].push_back(honnan);
        }
    }

    return tg;
}

void megjelol(int akt, int j, const Graf &g, std::vector<int> &jelek) {
    if (jelek[akt] & j) {
        return;
    }

    jelek[akt] |= j;
    for (auto sz : g[akt]) {
        megjelol(sz, j, g, jelek);
    }
}

std::vector<bool> erosen_osszefuggo_komponens(int kezd, const Graf &g) {
    const auto n = g.size();

    std::vector<int> jelek(n, 0);
    megjelol(kezd, 1, g, jelek);
    megjelol(kezd, 2, transzponalt(g), jelek);

    std::vector<bool> komponens(n);
    for (auto i = 0u; i < n; i++) {
        komponens[i] = jelek[i] == 3;
    }
    return komponens;
}

void celokat_felderit(int akt, const Graf &g, const std::vector<bool> &komponens, std::vector<bool> &lattam, std::vector<int> &celok) {
    if (lattam[akt]) {
        return;
    }
    lattam[akt] = true;

    if (komponens[akt]) {
        for (auto sz: g[akt]) {
            celokat_felderit(sz, g, komponens, lattam, celok);
        }
    }

    celok.push_back(akt);
}

void feldolgoz(int k, Graf &g) {
    const auto komponens = erosen_osszefuggo_komponens(k, g);

    const auto n = g.size();
    std::vector<bool> lattam(n, false);
    std::vector<int> celok;
    celokat_felderit(k, g, komponens, lattam, celok);
    celok.pop_back();

    using std::cout;

    cout << celok.size() << '\n';
    for (auto c: celok) {
        cout << c + 1 << ' ';
    }
    cout << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int k;
    Graf g;
    beolvas(std::cin, k, g);
    feldolgoz(k, g);

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1828 KiB
2Elfogadva0/013ms4432 KiB
3Elfogadva2/23ms2272 KiB
4Elfogadva2/23ms2472 KiB
5Elfogadva2/23ms2840 KiB
6Elfogadva2/23ms2784 KiB
7Elfogadva2/23ms2980 KiB
8Elfogadva2/23ms3244 KiB
9Elfogadva2/24ms3276 KiB
10Elfogadva2/24ms3296 KiB
11Elfogadva2/24ms3644 KiB
12Elfogadva2/28ms4156 KiB
13Elfogadva2/27ms4264 KiB
14Elfogadva2/212ms4744 KiB
15Elfogadva3/319ms6908 KiB
16Elfogadva4/420ms6920 KiB
17Elfogadva4/428ms7572 KiB
18Elfogadva3/326ms7636 KiB
19Elfogadva3/323ms7132 KiB
20Elfogadva3/354ms10292 KiB
21Elfogadva3/361ms10620 KiB
22Elfogadva3/363ms11076 KiB