162682025-04-19 10:35:12szilTurista járatokcpp17Wrong answer 20/100158ms28668 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200'001;

vector<pair<int, int>> g[MAXN];
vector<int> bct[MAXN];
vector<pair<int, int>> edges;
vector<int> st;
vector<vector<int>> comps;
bool is_cutpoint[MAXN], is_good[MAXN];
int tin[MAXN], low[MAXN], cid[MAXN], tin2[MAXN], timer = 1, th;
map<int, vector<int>> id_to_nodes;
vector<int> ans;

void dfs(int u, int p = -1) {
    int cnt = 0;
    tin[u] = low[u] = timer++;
    st.emplace_back(u);
    for (auto [v, _] : g[u]) {
        if (v == p) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= tin[u]) {
                is_cutpoint[u] = (tin[u] > 1 || tin[v] > 2);
                comps.push_back({u});
                while (st.back() != u) {
                    comps.back().push_back(st.back());
                    st.pop_back();
                }
            }
        }
    }
}

void dfs2(int u, int p = -1) {
    tin2[u] = timer++;
    for (int v : bct[u]) {
        if (v != p) {
            dfs2(v, u);
        }
    }
}

void dfs3(int u, int p = -1, bool g = false) {
    if (is_good[u]) g = 1;

    if (g) {
        for (int c : id_to_nodes[u]) ans.emplace_back(c);
    }

    for (int v : bct[u]) {
        if (v != p) dfs3(v, u, g);
    }
}

void solve() {
    int n, m, k; cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        edges.emplace_back(u, v);
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    dfs(1);
    int cc = 0;
    for (int i = 1; i <= n; i++) {
        if (is_cutpoint[i]) {
            cid[i] = ++cc;
            id_to_nodes[cc] = {i};
        }
    }

    th = cc;

    for (auto &vec : comps) {
        int id = ++cc;
        sort(vec.begin(), vec.end());
        id_to_nodes[id] = {};
        for (int u : vec) {
            for (auto [v, idx] : g[u]) {
                if (idx < k && binary_search(vec.begin(), vec.end(), v)) {
                    is_good[id] = 1;
                }
            }
            if (is_cutpoint[u]) {
                bct[id].emplace_back(cid[u]);
                bct[cid[u]].emplace_back(id);
            } else {
                id_to_nodes[id].emplace_back(u);
                cid[u] = id;
            }
        }
    }

    dfs2(cid[1]);
    for (int i = 0; i < k; i++) {
        auto [u, v] = edges[i];
        if (tin2[cid[u]] < tin2[cid[v]]) is_good[cid[v]] = 1;
        else is_good[cid[u]] = 1;
    }

    dfs3(cid[1]);
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    cout << ans.size() << "\n";
    for (int u : ans) cout << u << " ";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted8ms9820 KiB
2Accepted19ms11072 KiB
subtask20/10
3Wrong answer8ms9928 KiB
4Wrong answer10ms9780 KiB
5Accepted10ms9780 KiB
6Accepted9ms9780 KiB
7Wrong answer8ms9776 KiB
subtask310/10
8Accepted8ms9868 KiB
9Accepted8ms9780 KiB
10Accepted10ms9764 KiB
11Accepted12ms10028 KiB
12Accepted16ms11264 KiB
subtask410/10
13Accepted21ms12908 KiB
14Accepted10ms9780 KiB
15Accepted10ms9780 KiB
16Accepted9ms10036 KiB
17Accepted158ms28564 KiB
18Accepted56ms14588 KiB
19Accepted75ms15784 KiB
20Accepted56ms14672 KiB
subtask50/10
21Accepted17ms11060 KiB
22Accepted8ms9780 KiB
23Wrong answer10ms9784 KiB
24Accepted10ms9780 KiB
25Accepted94ms20388 KiB
26Accepted17ms10484 KiB
27Accepted14ms10576 KiB
subtask60/60
28Accepted8ms9780 KiB
29Accepted10ms9780 KiB
30Accepted13ms10036 KiB
31Accepted10ms10036 KiB
32Wrong answer12ms10348 KiB
33Accepted13ms10340 KiB
34Accepted19ms10960 KiB
35Accepted20ms11164 KiB
36Accepted17ms10964 KiB
37Accepted151ms28668 KiB
38Accepted59ms14656 KiB
39Accepted59ms14512 KiB
40Accepted54ms14476 KiB
41Accepted61ms14500 KiB
42Accepted59ms14500 KiB
43Accepted56ms14508 KiB
44Accepted56ms14576 KiB
45Accepted82ms15884 KiB
46Accepted61ms14500 KiB
47Accepted57ms14480 KiB
48Accepted57ms14420 KiB
49Accepted54ms14620 KiB
50Accepted57ms14516 KiB