162712025-04-19 10:51:47szilTurista járatokcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva24ms23808 KiB
2Elfogadva28ms25152 KiB
subtask210/10
3Elfogadva25ms23860 KiB
4Elfogadva26ms23860 KiB
5Elfogadva19ms24088 KiB
6Elfogadva19ms23892 KiB
7Elfogadva24ms24044 KiB
subtask310/10
8Elfogadva19ms23856 KiB
9Elfogadva19ms23856 KiB
10Elfogadva26ms23860 KiB
11Elfogadva26ms24116 KiB
12Elfogadva28ms25588 KiB
subtask410/10
13Elfogadva39ms26992 KiB
14Elfogadva19ms24092 KiB
15Elfogadva25ms23860 KiB
16Elfogadva20ms24116 KiB
17Elfogadva159ms43248 KiB
18Elfogadva65ms28588 KiB
19Elfogadva90ms29864 KiB
20Elfogadva75ms28584 KiB
subtask510/10
21Elfogadva28ms25204 KiB
22Elfogadva20ms23936 KiB
23Elfogadva25ms23860 KiB
24Elfogadva26ms24016 KiB
25Elfogadva109ms34420 KiB
26Elfogadva26ms24644 KiB
27Elfogadva30ms24628 KiB
subtask660/60
28Elfogadva25ms23860 KiB
29Elfogadva20ms23928 KiB
30Elfogadva27ms24172 KiB
31Elfogadva21ms24116 KiB
32Elfogadva28ms24372 KiB
33Elfogadva24ms24364 KiB
34Elfogadva28ms25188 KiB
35Elfogadva35ms25140 KiB
36Elfogadva28ms25016 KiB
37Elfogadva181ms43316 KiB
38Elfogadva75ms28804 KiB
39Elfogadva67ms28588 KiB
40Elfogadva67ms28844 KiB
41Elfogadva78ms28580 KiB
42Elfogadva67ms28576 KiB
43Elfogadva68ms28580 KiB
44Elfogadva75ms28688 KiB
45Elfogadva94ms30020 KiB
46Elfogadva68ms28804 KiB
47Elfogadva67ms28836 KiB
48Elfogadva75ms28580 KiB
49Elfogadva72ms28580 KiB
50Elfogadva64ms28604 KiB