32822023-02-23 20:39:23zsomborElfogáscpp17Elfogadva 50/5057ms11132 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ÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/04ms3104 KiB
2Elfogadva0/010ms4620 KiB
3Elfogadva2/23ms3516 KiB
4Elfogadva2/24ms3496 KiB
5Elfogadva2/24ms3740 KiB
6Elfogadva2/24ms3836 KiB
7Elfogadva3/34ms4044 KiB
8Elfogadva3/34ms4516 KiB
9Elfogadva3/36ms4352 KiB
10Elfogadva3/36ms4608 KiB
11Elfogadva3/38ms5408 KiB
12Elfogadva3/39ms5752 KiB
13Elfogadva3/310ms6004 KiB
14Elfogadva3/312ms6588 KiB
15Elfogadva3/312ms6976 KiB
16Elfogadva3/341ms8212 KiB
17Elfogadva3/343ms8828 KiB
18Elfogadva3/343ms8816 KiB
19Elfogadva3/343ms8808 KiB
20Elfogadva3/357ms11132 KiB