166182025-05-06 22:05:24algoproTurista járatokcpp17Accepted 100/100184ms43232 KiB
// UUID: d41603da-7955-4de5-9509-1bb68de6a2c6
#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
1Accepted18ms24052 KiB
2Accepted34ms25140 KiB
subtask210/10
3Accepted25ms23916 KiB
4Accepted19ms23860 KiB
5Accepted25ms23876 KiB
6Accepted19ms24052 KiB
7Accepted19ms23860 KiB
subtask310/10
8Accepted25ms23860 KiB
9Accepted19ms23860 KiB
10Accepted19ms23864 KiB
11Accepted26ms24240 KiB
12Accepted32ms25420 KiB
subtask410/10
13Accepted34ms27024 KiB
14Accepted19ms23872 KiB
15Accepted26ms23860 KiB
16Accepted27ms24116 KiB
17Accepted158ms43232 KiB
18Accepted67ms28584 KiB
19Accepted90ms29860 KiB
20Accepted75ms28836 KiB
subtask510/10
21Accepted34ms25108 KiB
22Accepted19ms23860 KiB
23Accepted25ms23872 KiB
24Accepted20ms23860 KiB
25Accepted108ms34472 KiB
26Accepted27ms24824 KiB
27Accepted26ms24628 KiB
subtask660/60
28Accepted20ms23872 KiB
29Accepted26ms23860 KiB
30Accepted26ms24116 KiB
31Accepted23ms24116 KiB
32Accepted28ms24372 KiB
33Accepted24ms24372 KiB
34Accepted34ms25140 KiB
35Accepted29ms25140 KiB
36Accepted28ms25068 KiB
37Accepted184ms43208 KiB
38Accepted74ms28820 KiB
39Accepted67ms28580 KiB
40Accepted67ms28648 KiB
41Accepted76ms28584 KiB
42Accepted67ms28720 KiB
43Accepted67ms28760 KiB
44Accepted68ms28580 KiB
45Accepted86ms29868 KiB
46Accepted75ms28816 KiB
47Accepted75ms28748 KiB
48Accepted74ms28580 KiB
49Accepted67ms28584 KiB
50Accepted67ms28804 KiB