83462024-01-14 20:26:11kukkermanKerékpártúra (50 pont)cpp17Accepted 50/50140ms11932 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

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

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

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

Graf transzponalt_graf(const Graf &g) {
    const int n = static_cast<int>(g.size());
    Graf tg(n);

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

    return tg;
}

void dfs(int akt, const Graf &ki_graf, std::vector<bool> &lattam, std::vector<int> &sorrend) {
    if (!lattam[akt]) {
        lattam[akt] = true;

        for (auto ki_szomszed : ki_graf[akt]) {
            dfs(ki_szomszed, ki_graf, lattam, sorrend);
        }
        
        sorrend.push_back(akt);
    }
}

void hozzarendel(int akt, int akt_komp, const Graf &be_graf, std::vector<int> &komponens) {
    if (komponens[akt] == -1) {
        komponens[akt] = akt_komp;

        for (auto be_szomszed : be_graf[akt]) {
            hozzarendel(be_szomszed, akt_komp, be_graf, komponens);
        }
    }
}

std::vector<int> vegpontok(int kezd, const Graf &ki_graf, std::vector<int> &komponens) {
    const auto n = ki_graf.size();
    std::vector<bool> lattam(n, false);
    std::vector<int> v;

    std::deque<int> q;
    q.push_back(kezd);
    while (!q.empty()) {
        const auto akt = q.front();
        q.pop_front();

        if (!lattam[akt]) {
            lattam[akt] = true;
            v.push_back(akt);

            if (komponens[akt] == komponens[kezd]) {
                for (auto szomszed : ki_graf[akt]) {
                    q.push_back(szomszed);
                }
            }
        }
    }

    return v;
}

void feldolgoz(const Graf &ki_graf, int kezd) {
    const auto n = ki_graf.size();

    std::vector<bool> lattam(n, false);
    std::vector<int> sorrend;
    dfs(kezd, ki_graf, lattam, sorrend);
    
    const auto be_graf = transzponalt_graf(ki_graf);
    std::vector<int> komponens(n, -1);
    std::reverse(sorrend.begin(), sorrend.end());
    for (auto p : sorrend) {
        hozzarendel(p, p, be_graf, komponens);
    }

    auto v = vegpontok(kezd, ki_graf, komponens);
    std::swap(v.front(), v.back());
    v.pop_back();

    std::cout << v.size() << '\n';
    for (auto p : v) {
        std::cout << p + 1 << ' ';
    }
    std::cout << '\n';
}

int main() {
    Graf ki_graf;
    int kezd;
    beolvas(std::cin, ki_graf, kezd);
    
    feldolgoz(ki_graf, kezd);

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1808 KiB
2Accepted0/023ms4788 KiB
3Accepted2/23ms2212 KiB
4Accepted2/23ms2424 KiB
5Accepted2/23ms2640 KiB
6Accepted2/23ms3008 KiB
7Accepted2/23ms3256 KiB
8Accepted2/24ms3284 KiB
9Accepted2/24ms3700 KiB
10Accepted2/24ms3648 KiB
11Accepted2/27ms3844 KiB
12Accepted2/214ms4144 KiB
13Accepted2/213ms4236 KiB
14Accepted2/224ms4752 KiB
15Accepted3/337ms7480 KiB
16Accepted4/441ms7404 KiB
17Accepted4/457ms8520 KiB
18Accepted3/350ms8496 KiB
19Accepted3/345ms8212 KiB
20Accepted3/3125ms11504 KiB
21Accepted3/3138ms11664 KiB
22Accepted3/3140ms11932 KiB