8257 2024. 01. 13 20:41:43 szil Kerékpártúra (50 pont) cpp17 Elfogadva 50/50 70ms 10956 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 10'001;

vector<int> g[MAXN], g2[MAXN];
bool vis[MAXN]; int scc[MAXN];
stack<int> order;

void dfs1(int u) {
    vis[u]=1;
    for (int v : g[u]) {
        if (!vis[v]) dfs1(v);
    }
    order.push(u);
}

void dfs2(int u, int comp) {
    scc[u] = comp;
    for (int v : g2[u]) {
        if (scc[v] == 0) dfs2(v, comp);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, st; cin >> n >> m >> st;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        g[a].emplace_back(b);
        g2[b].emplace_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs1(i);
    }

    int timer = 0;
    while (!order.empty()) {
        int u = order.top(); order.pop();
        if (scc[u] == 0) {
            dfs2(u, ++timer);
        }
    }
    set<int> ans;
    for (int i = 1; i <= n; i++) {
        if (scc[i] == scc[st]) {
            for (int u : g[i]) ans.insert(u);
        }
    }
    auto it = ans.find(st);
    if (it != ans.end()) ans.erase(it);
    cout << ans.size() << "\n";
    for (int u : ans) cout << u << " ";
    cout << "\n";
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 2968 KiB
2 Elfogadva 0/0 13ms 4936 KiB
3 Elfogadva 2/2 3ms 3332 KiB
4 Elfogadva 2/2 3ms 3236 KiB
5 Elfogadva 2/2 3ms 3704 KiB
6 Elfogadva 2/2 3ms 3524 KiB
7 Elfogadva 2/2 3ms 3712 KiB
8 Elfogadva 2/2 4ms 3848 KiB
9 Elfogadva 2/2 4ms 3860 KiB
10 Elfogadva 2/2 4ms 4008 KiB
11 Elfogadva 2/2 4ms 4216 KiB
12 Elfogadva 2/2 8ms 4500 KiB
13 Elfogadva 2/2 8ms 4664 KiB
14 Elfogadva 2/2 12ms 5156 KiB
15 Elfogadva 3/3 20ms 7008 KiB
16 Elfogadva 4/4 23ms 7360 KiB
17 Elfogadva 4/4 32ms 8408 KiB
18 Elfogadva 3/3 28ms 7856 KiB
19 Elfogadva 3/3 27ms 7928 KiB
20 Elfogadva 3/3 57ms 10244 KiB
21 Elfogadva 3/3 68ms 10448 KiB
22 Elfogadva 3/3 70ms 10956 KiB