8312 2024. 01. 14 17:08:13 TuruTamas Kerékpártúra (50 pont) cpp17 Elfogadva 50/50 149ms 16196 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll N, M, K, a, b, current_comp;
vector<vector<ll>> G, iG;
vector<ll> top, comp_of;
vector<bool> vis;
set<ll> ans;

void dfs1(ll x) {
    vis[x] = true;
    for (ll next : G[x]) {
        if (!vis[next]) {
            dfs1(next);
        }
    }
    top.push_back(x);
}

void dfs2(ll x) {
    comp_of[x] = current_comp;
    vis[x] = true;
    for(ll next : iG[x]) {
        if (!vis[next]) {
            dfs2(next);
        }
    }
}

int main()
{
    cin >> N >> M >> K;
    K--;

    G.resize(N);
    iG.resize(N);
    for (ll m = 0; m < M; m++) {
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        iG[b].push_back(a);
    }

    vis.assign(N, false);
    for (ll n = 0; n < N; n++) {
        if (!vis[n]) {
            dfs1(n);
        }
    }

    vis.assign(N, false);
    comp_of.resize(N);
    reverse(top.begin(), top.end());
    for (ll x : top) {
        if (!vis[x]) {
            dfs2(x);
            current_comp++;
        }
    }

    for (ll n = 0; n < N; n++) {
        if (comp_of[n] == comp_of[K]) {
            ans.insert(n);
            for (ll nb : G[n]) {
                ans.insert(nb);
            }
        }
    }

    cout << ans.size()-1 << "\n";
    for (ll c : ans) {
        if (c != K) {
            cout << c+1 << " ";
        }
    }
    cout << endl;
}

Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1872 KiB
2 Elfogadva 0/0 23ms 5352 KiB
3 Elfogadva 2/2 3ms 2284 KiB
4 Elfogadva 2/2 3ms 2500 KiB
5 Elfogadva 2/2 3ms 2608 KiB
6 Elfogadva 2/2 3ms 2968 KiB
7 Elfogadva 2/2 3ms 3016 KiB
8 Elfogadva 2/2 4ms 3348 KiB
9 Elfogadva 2/2 4ms 3268 KiB
10 Elfogadva 2/2 4ms 3580 KiB
11 Elfogadva 2/2 7ms 3760 KiB
12 Elfogadva 2/2 13ms 4328 KiB
13 Elfogadva 2/2 13ms 4600 KiB
14 Elfogadva 2/2 24ms 5732 KiB
15 Elfogadva 3/3 39ms 8492 KiB
16 Elfogadva 4/4 45ms 9148 KiB
17 Elfogadva 4/4 63ms 10996 KiB
18 Elfogadva 3/3 54ms 9852 KiB
19 Elfogadva 3/3 48ms 10016 KiB
20 Elfogadva 3/3 126ms 15340 KiB
21 Elfogadva 3/3 145ms 15996 KiB
22 Elfogadva 3/3 149ms 16196 KiB