82572024-01-13 20:41:43szilKerékpártúra (50 pont)cpp17Accepted 50/5070ms10956 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms2968 KiB
2Accepted0/013ms4936 KiB
3Accepted2/23ms3332 KiB
4Accepted2/23ms3236 KiB
5Accepted2/23ms3704 KiB
6Accepted2/23ms3524 KiB
7Accepted2/23ms3712 KiB
8Accepted2/24ms3848 KiB
9Accepted2/24ms3860 KiB
10Accepted2/24ms4008 KiB
11Accepted2/24ms4216 KiB
12Accepted2/28ms4500 KiB
13Accepted2/28ms4664 KiB
14Accepted2/212ms5156 KiB
15Accepted3/320ms7008 KiB
16Accepted4/423ms7360 KiB
17Accepted4/432ms8408 KiB
18Accepted3/328ms7856 KiB
19Accepted3/327ms7928 KiB
20Accepted3/357ms10244 KiB
21Accepted3/368ms10448 KiB
22Accepted3/370ms10956 KiB