162702025-04-19 10:43:39szilTurista járatokcpp17Hibás válasz 30/100180ms42748 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]) {
            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
1Elfogadva18ms23860 KiB
2Elfogadva34ms25140 KiB
subtask210/10
3Elfogadva25ms23860 KiB
4Elfogadva19ms23948 KiB
5Elfogadva26ms23864 KiB
6Elfogadva19ms23860 KiB
7Elfogadva18ms23860 KiB
subtask310/10
8Elfogadva25ms23860 KiB
9Elfogadva19ms23872 KiB
10Elfogadva19ms23816 KiB
11Elfogadva26ms24116 KiB
12Elfogadva26ms25396 KiB
subtask410/10
13Elfogadva39ms26992 KiB
14Elfogadva19ms23860 KiB
15Elfogadva25ms23860 KiB
16Elfogadva20ms24140 KiB
17Elfogadva173ms42644 KiB
18Elfogadva74ms28580 KiB
19Elfogadva83ms29860 KiB
20Elfogadva68ms28536 KiB
subtask50/10
21Elfogadva35ms25140 KiB
22Elfogadva19ms23860 KiB
23Hibás válasz20ms23860 KiB
24Elfogadva25ms23872 KiB
25Elfogadva108ms34360 KiB
26Elfogadva26ms24640 KiB
27Elfogadva26ms24632 KiB
subtask60/60
28Elfogadva20ms23860 KiB
29Elfogadva20ms23860 KiB
30Elfogadva27ms24116 KiB
31Elfogadva28ms24116 KiB
32Hibás válasz23ms24372 KiB
33Elfogadva24ms24372 KiB
34Elfogadva28ms25136 KiB
35Elfogadva34ms25296 KiB
36Elfogadva28ms25140 KiB
37Elfogadva180ms42748 KiB
38Elfogadva74ms28736 KiB
39Elfogadva67ms28576 KiB
40Elfogadva67ms28840 KiB
41Elfogadva67ms28736 KiB
42Elfogadva76ms28584 KiB
43Elfogadva67ms28584 KiB
44Elfogadva75ms28584 KiB
45Elfogadva94ms29860 KiB
46Elfogadva67ms28580 KiB
47Elfogadva67ms28584 KiB
48Elfogadva67ms28688 KiB
49Elfogadva72ms28596 KiB
50Elfogadva65ms28756 KiB