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