83122024-01-14 17:08:13TuruTamasKerékpártúra (50 pont)cpp17Elfogadva 50/50149ms16196 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ÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1872 KiB
2Elfogadva0/023ms5352 KiB
3Elfogadva2/23ms2284 KiB
4Elfogadva2/23ms2500 KiB
5Elfogadva2/23ms2608 KiB
6Elfogadva2/23ms2968 KiB
7Elfogadva2/23ms3016 KiB
8Elfogadva2/24ms3348 KiB
9Elfogadva2/24ms3268 KiB
10Elfogadva2/24ms3580 KiB
11Elfogadva2/27ms3760 KiB
12Elfogadva2/213ms4328 KiB
13Elfogadva2/213ms4600 KiB
14Elfogadva2/224ms5732 KiB
15Elfogadva3/339ms8492 KiB
16Elfogadva4/445ms9148 KiB
17Elfogadva4/463ms10996 KiB
18Elfogadva3/354ms9852 KiB
19Elfogadva3/348ms10016 KiB
20Elfogadva3/3126ms15340 KiB
21Elfogadva3/3145ms15996 KiB
22Elfogadva3/3149ms16196 KiB