202122026-01-04 23:47:40hunzombiKerékpártúra (50 pont)cpp17Accepted 50/50137ms4148 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<int> order, group_id;
vector<vector<int>> graph, r_graph, group_nodes;

void dfs1(int node, vector<bool>& visited) {
    visited[node] = true;
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs1(next, visited);
        }
    }
    order.push_back(node);
}

void dfs2(int node, int group, vector<int>& components) {
    group_id[node] = group;
    components.push_back(node);
    for (int next : r_graph[node]) {
        if (group_id[next] == -1) {
            dfs2(next, group, components);
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    graph.assign(n + 1, vector<int>());
    r_graph.assign(n + 1, vector<int>());
    group_id.assign(n + 1, -1);

    for (int i=0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        r_graph[v].push_back(u);
    }

    vector<bool> visited(n + 1, false);

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

    reverse(order.begin(), order.end());
    int cnt = 0;
    for (int x : order) {
        vector<int> comps(0);
        if (group_id[x] == -1) {
            dfs2(x, cnt, comps);
            group_nodes.push_back(comps);
            cnt++;
        }
    }

    vector<int> ans;
    vector<bool> sz(n + 1, false);
    sz[k] = true;

    for (int node : group_nodes[group_id[k]]) {
        if (!sz[node]) {
            ans.push_back(node);
            sz[node] = true;
        }
        for (int next : graph[node]) {
            if (!sz[next]) {
                ans.push_back(next);
                sz[next] = true;
            }
        }
    }

    cout << ans.size() << '\n';
    for (int x : ans) {
        cout << x << ' ';
    }

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms512 KiB
2Accepted0/023ms1844 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/21ms316 KiB
8Accepted2/23ms552 KiB
9Accepted2/23ms316 KiB
10Accepted2/24ms436 KiB
11Accepted2/24ms544 KiB
12Accepted2/212ms692 KiB
13Accepted2/210ms564 KiB
14Accepted2/221ms944 KiB
15Accepted3/337ms2332 KiB
16Accepted4/439ms2320 KiB
17Accepted4/456ms2748 KiB
18Accepted3/350ms2492 KiB
19Accepted3/343ms2612 KiB
20Accepted3/3120ms3876 KiB
21Accepted3/3136ms4016 KiB
22Accepted3/3137ms4148 KiB