162712025-04-19 10:51:47szilTurista járatokcpp17Accepted 100/100181ms43316 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 (comps.back().back() != v) {
                    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]) {
            if (c != 1) 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
1Accepted24ms23808 KiB
2Accepted28ms25152 KiB
subtask210/10
3Accepted25ms23860 KiB
4Accepted26ms23860 KiB
5Accepted19ms24088 KiB
6Accepted19ms23892 KiB
7Accepted24ms24044 KiB
subtask310/10
8Accepted19ms23856 KiB
9Accepted19ms23856 KiB
10Accepted26ms23860 KiB
11Accepted26ms24116 KiB
12Accepted28ms25588 KiB
subtask410/10
13Accepted39ms26992 KiB
14Accepted19ms24092 KiB
15Accepted25ms23860 KiB
16Accepted20ms24116 KiB
17Accepted159ms43248 KiB
18Accepted65ms28588 KiB
19Accepted90ms29864 KiB
20Accepted75ms28584 KiB
subtask510/10
21Accepted28ms25204 KiB
22Accepted20ms23936 KiB
23Accepted25ms23860 KiB
24Accepted26ms24016 KiB
25Accepted109ms34420 KiB
26Accepted26ms24644 KiB
27Accepted30ms24628 KiB
subtask660/60
28Accepted25ms23860 KiB
29Accepted20ms23928 KiB
30Accepted27ms24172 KiB
31Accepted21ms24116 KiB
32Accepted28ms24372 KiB
33Accepted24ms24364 KiB
34Accepted28ms25188 KiB
35Accepted35ms25140 KiB
36Accepted28ms25016 KiB
37Accepted181ms43316 KiB
38Accepted75ms28804 KiB
39Accepted67ms28588 KiB
40Accepted67ms28844 KiB
41Accepted78ms28580 KiB
42Accepted67ms28576 KiB
43Accepted68ms28580 KiB
44Accepted75ms28688 KiB
45Accepted94ms30020 KiB
46Accepted68ms28804 KiB
47Accepted67ms28836 KiB
48Accepted75ms28580 KiB
49Accepted72ms28580 KiB
50Accepted64ms28604 KiB