8312 | 2024. 01. 14 17:08:13 | TuruTamas | Kerékpártúra (50 pont) | cpp17 | Elfogadva 50/50 | 149ms | 16196 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1872 KiB | |||
2 | Elfogadva | 0/0 | 23ms | 5352 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2284 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2500 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2608 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2968 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3016 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3348 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3268 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 3580 KiB | |||
11 | Elfogadva | 2/2 | 7ms | 3760 KiB | |||
12 | Elfogadva | 2/2 | 13ms | 4328 KiB | |||
13 | Elfogadva | 2/2 | 13ms | 4600 KiB | |||
14 | Elfogadva | 2/2 | 24ms | 5732 KiB | |||
15 | Elfogadva | 3/3 | 39ms | 8492 KiB | |||
16 | Elfogadva | 4/4 | 45ms | 9148 KiB | |||
17 | Elfogadva | 4/4 | 63ms | 10996 KiB | |||
18 | Elfogadva | 3/3 | 54ms | 9852 KiB | |||
19 | Elfogadva | 3/3 | 48ms | 10016 KiB | |||
20 | Elfogadva | 3/3 | 126ms | 15340 KiB | |||
21 | Elfogadva | 3/3 | 145ms | 15996 KiB | |||
22 | Elfogadva | 3/3 | 149ms | 16196 KiB |