166182025-05-06 22:05:24algoproTurista járatokcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva18ms24052 KiB
2Elfogadva34ms25140 KiB
subtask210/10
3Elfogadva25ms23916 KiB
4Elfogadva19ms23860 KiB
5Elfogadva25ms23876 KiB
6Elfogadva19ms24052 KiB
7Elfogadva19ms23860 KiB
subtask310/10
8Elfogadva25ms23860 KiB
9Elfogadva19ms23860 KiB
10Elfogadva19ms23864 KiB
11Elfogadva26ms24240 KiB
12Elfogadva32ms25420 KiB
subtask410/10
13Elfogadva34ms27024 KiB
14Elfogadva19ms23872 KiB
15Elfogadva26ms23860 KiB
16Elfogadva27ms24116 KiB
17Elfogadva158ms43232 KiB
18Elfogadva67ms28584 KiB
19Elfogadva90ms29860 KiB
20Elfogadva75ms28836 KiB
subtask510/10
21Elfogadva34ms25108 KiB
22Elfogadva19ms23860 KiB
23Elfogadva25ms23872 KiB
24Elfogadva20ms23860 KiB
25Elfogadva108ms34472 KiB
26Elfogadva27ms24824 KiB
27Elfogadva26ms24628 KiB
subtask660/60
28Elfogadva20ms23872 KiB
29Elfogadva26ms23860 KiB
30Elfogadva26ms24116 KiB
31Elfogadva23ms24116 KiB
32Elfogadva28ms24372 KiB
33Elfogadva24ms24372 KiB
34Elfogadva34ms25140 KiB
35Elfogadva29ms25140 KiB
36Elfogadva28ms25068 KiB
37Elfogadva184ms43208 KiB
38Elfogadva74ms28820 KiB
39Elfogadva67ms28580 KiB
40Elfogadva67ms28648 KiB
41Elfogadva76ms28584 KiB
42Elfogadva67ms28720 KiB
43Elfogadva67ms28760 KiB
44Elfogadva68ms28580 KiB
45Elfogadva86ms29868 KiB
46Elfogadva75ms28816 KiB
47Elfogadva75ms28748 KiB
48Elfogadva74ms28580 KiB
49Elfogadva67ms28584 KiB
50Elfogadva67ms28804 KiB