82772024-01-14 08:53:50MagyarKendeSZLGKerékpártúra (50 pont)cpp17Időlimit túllépés 24/50500ms4888 KiB
#include <bits/stdc++.h>
#define speed cin.tie(0); ios::sync_with_stdio(0)
using namespace std;

vector<vector<int>> g;
int N, M, K;
vector<bool> cache;

bool goback(int s) {
    vector<bool> vis(N + 1);
    vector<int> from(N + 1);
    queue<int> q;
    vis[s] = 1;
    q.push(s);

    while (!q.empty()) {
        int node = q.front(); q.pop();

        if (cache[node]) {
            return 1;
        }

        if (node == K) {
            int curr = node;
            do {
                cache[curr] = 1;
                curr = from[curr];
            } while (curr);

            return 1;
        }

        for (int neigh : g[node]) {
            if (!vis[neigh]) {
                vis[neigh] = 1;
                from[neigh] = node;
                q.push(neigh);
            }
        }
    }

    return 0;
}

int main()
{
    speed;

    cin >> N >> M >> K;

    g.resize(N + 1);
    while (M--) {
        int U, V;
        cin >> U >> V;
        g[U].push_back(V);
    }

    vector<bool> vis(N + 1);
    queue<int> q;
    q.push(K);
    vis[K] = 1;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (int neigh : g[node]) {
            if (!vis[neigh]) {
                q.push(neigh);
                vis[neigh] = 1;
            }
        }
    }

    vector<int> base;

    cache.resize(N + 1);

    for (int i = 1; i <= N; i++) {
        if (i != K && vis[i] && goback(i)) {
            base.push_back(i);
        }
    }

    unordered_set<int> result;
    for (int x : base) {
        result.insert(x);
        for (int neigh : g[x]) {
            if (neigh != K) result.insert(neigh);
        }
    }

    for (int neigh : g[K]) {
        result.insert(neigh);
    }

    if (result.empty()) {
        cout << 0;
        exit(0);
    }

    cout << result.size() << '\n';

    for (int x : result) cout << x << ' ';
    cout << '\n';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base24/50
1Elfogadva0/03ms1832 KiB
2Időlimit túllépés0/0500ms2040 KiB
3Elfogadva2/23ms2256 KiB
4Elfogadva2/23ms2432 KiB
5Elfogadva2/23ms2644 KiB
6Elfogadva2/23ms2684 KiB
7Elfogadva2/23ms2744 KiB
8Elfogadva2/24ms2772 KiB
9Elfogadva2/23ms2776 KiB
10Elfogadva2/24ms2920 KiB
11Elfogadva2/243ms3144 KiB
12Elfogadva2/235ms3352 KiB
13Elfogadva2/265ms3284 KiB
14Elfogadva2/2108ms3796 KiB
15Időlimit túllépés0/3439ms3160 KiB
16Időlimit túllépés0/4474ms3440 KiB
17Időlimit túllépés0/4458ms3368 KiB
18Időlimit túllépés0/3455ms3524 KiB
19Időlimit túllépés0/3469ms3484 KiB
20Időlimit túllépés0/3500ms4208 KiB
21Időlimit túllépés0/3455ms4708 KiB
22Időlimit túllépés0/3465ms4888 KiB