3282 2023. 02. 23 20:39:23 zsombor Elfogás cpp17 Elfogadva 50/50 57ms 11132 KiB
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, u, v, a, b;
vector <vector <int>> g(2e4 + 1);
vector <int> d(2e4 + 1, -1);
vector <int> p(2e4 + 1, -1);
vector <int> up(2e4 + 1, 0);
vector <bool> elv(2e4 + 1, false);
vector <int> ans;

void dfs(int x) {
    up[x] = d[x];
    for (int i : g[x]) {
        if (d[i] > -1) { up[x] = min(up[x], d[i]); continue; }
        d[i] = d[x] + 1;
        p[i] = x;
        dfs(i);
        up[x] = min(up[x], up[i]);
        if (up[i] >= d[x]) elv[x] = true;
        if (i == v && up[i] < d[x]) v = x;
    }
}

void dfs2(int x) {
    ans.push_back(x);
    for (int i : g[x]) if (d[i] == d[x] + 1) dfs2(i);
}

int main()
{
    cin >> n >> m >> u >> v;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    d[u] = p[u] = 0;
    dfs(u);

    /*for (int i = 1; i <= n; i++) cout << i << " ";
    cout << endl;
    for (int i = 1; i <= n; i++) cout << d[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i++) cout << up[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i++) cout << elv[i] << " ";
    cout << endl;
    cout << v << endl;*/

    dfs2(v);
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int i : ans) cout << i << " ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 4ms 3104 KiB
2 Elfogadva 0/0 10ms 4620 KiB
3 Elfogadva 2/2 3ms 3516 KiB
4 Elfogadva 2/2 4ms 3496 KiB
5 Elfogadva 2/2 4ms 3740 KiB
6 Elfogadva 2/2 4ms 3836 KiB
7 Elfogadva 3/3 4ms 4044 KiB
8 Elfogadva 3/3 4ms 4516 KiB
9 Elfogadva 3/3 6ms 4352 KiB
10 Elfogadva 3/3 6ms 4608 KiB
11 Elfogadva 3/3 8ms 5408 KiB
12 Elfogadva 3/3 9ms 5752 KiB
13 Elfogadva 3/3 10ms 6004 KiB
14 Elfogadva 3/3 12ms 6588 KiB
15 Elfogadva 3/3 12ms 6976 KiB
16 Elfogadva 3/3 41ms 8212 KiB
17 Elfogadva 3/3 43ms 8828 KiB
18 Elfogadva 3/3 43ms 8816 KiB
19 Elfogadva 3/3 43ms 8808 KiB
20 Elfogadva 3/3 57ms 11132 KiB