162692025-04-19 10:39:18szilTurista járatokcpp17Wrong answer 20/100162ms42716 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 500'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
1Accepted24ms23860 KiB
2Accepted28ms25140 KiB
subtask20/10
3Wrong answer25ms23860 KiB
4Wrong answer25ms23800 KiB
5Accepted19ms23860 KiB
6Accepted19ms24052 KiB
7Wrong answer23ms23740 KiB
subtask310/10
8Accepted24ms24076 KiB
9Accepted25ms23860 KiB
10Accepted19ms23860 KiB
11Accepted20ms24116 KiB
12Accepted25ms25300 KiB
subtask410/10
13Accepted39ms27116 KiB
14Accepted19ms23812 KiB
15Accepted25ms23860 KiB
16Accepted20ms24116 KiB
17Accepted157ms42716 KiB
18Accepted65ms28616 KiB
19Accepted92ms29968 KiB
20Accepted75ms28584 KiB
subtask50/10
21Accepted35ms25140 KiB
22Accepted19ms23860 KiB
23Wrong answer19ms23860 KiB
24Accepted25ms23952 KiB
25Accepted108ms34464 KiB
26Accepted26ms24628 KiB
27Accepted26ms24628 KiB
subtask60/60
28Accepted20ms23860 KiB
29Accepted20ms23860 KiB
30Accepted21ms24080 KiB
31Accepted27ms24116 KiB
32Wrong answer28ms24240 KiB
33Accepted25ms24388 KiB
34Accepted28ms25248 KiB
35Accepted35ms25300 KiB
36Accepted34ms25136 KiB
37Accepted162ms42648 KiB
38Accepted75ms28740 KiB
39Accepted65ms28704 KiB
40Accepted72ms28840 KiB
41Accepted75ms28580 KiB
42Accepted68ms28580 KiB
43Accepted67ms28576 KiB
44Accepted74ms28580 KiB
45Accepted96ms29932 KiB
46Accepted68ms28628 KiB
47Accepted68ms28584 KiB
48Accepted75ms28580 KiB
49Accepted65ms28660 KiB
50Accepted72ms28596 KiB