57342023-09-10 17:40:42kukkermanA lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 40/40361ms24112 KiB
#include <iostream>
#include <vector>
#include <unordered_set>
#include <deque>
#include <algorithm>

void beolvas(std::istream &in, size_t &ind, size_t &erk, std::vector<std::vector<size_t>> &vonalak) {
    size_t n, m;
    in >> n >> m >> ind >> erk;

    vonalak.resize(n);
    for (auto i = 0u; i < n; i++) {
        size_t a;
        in >> a;

        vonalak[i].resize(a);
        for (auto j = 0u; j < a; j++) {
            in >> vonalak[i][j];
        }
    }
}

bool van_kozos_allomas(const std::vector<size_t> &vonal1, const std::vector<size_t> &vonal2) {
    const auto h1 = vonal1.size();
    const auto h2 = vonal2.size();

    auto i = 0u;
    auto j = 0u;
    while (i < h1 && j < h2 && vonal1[i] != vonal2[j]) {
        if (vonal1[i] < vonal2[j]) {
            i++;
        } else {
            j++;
        }
    }

    return i < h1 && j < h2;
}

void feldolgoz(size_t ind, size_t erk, std::vector<std::vector<size_t>> &vonalak) {
    const auto n = vonalak.size();

    std::vector<bool> erk_vonal(n, false);
    std::deque<std::pair<size_t, size_t>> sor;

    for (auto v = 0u; v < n; v++) {
        for (auto a : vonalak[v]) {
            if (a == ind) {
                sor.emplace_back(v, v);

            } else if (a == erk) {
                erk_vonal[v] = true;
            }
        }

        std::sort(vonalak[v].begin(), vonalak[v].end());
    }

    std::vector<std::unordered_set<size_t>> sz(n);
    for (auto v1 = 0u; v1 < n - 1; v1++) {
        for (auto v2 = v1 + 1; v2 < n; v2++) {
            if (van_kozos_allomas(vonalak[v1], vonalak[v2])) {
                sz[v1].insert(v2);
                sz[v2].insert(v1);
            }
        }
    }

    std::vector<size_t> elozo_vonal(n, n);
    std::vector<size_t> utvonal;
    while (!sor.empty() && utvonal.empty()) {
        const auto [v, elozo] = sor.front();
        sor.pop_front();

        if (elozo_vonal[v] == n) {
            elozo_vonal[v] = elozo;

            if (erk_vonal[v]) {
                size_t i = v;
                while (elozo_vonal[i] != i) {
                    utvonal.push_back(i);
                    i = elozo_vonal[i];
                }
                utvonal.push_back(i);

            } else {
                for (auto csatl : sz[v]) {
                    sor.emplace_back(csatl, v);
                }
            }
        }
    }

    if (!utvonal.empty()) {
        const auto hossz = utvonal.size();
        std::cout << hossz << std::endl;
        for (auto i = 1u; i <= hossz; i++) {
            std::cout << utvonal[hossz - i] + 1 << ' ';
        }

    } else {
        std::cout << -1;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<std::vector<size_t>> vonalak;
    size_t ind, erk;

    beolvas(std::cin, ind, erk, vonalak);
    feldolgoz(ind, erk, vonalak);

    return 0;
}