162682025-04-19 10:35:12szilTurista járatokcpp17Hibás válasz 20/100158ms28668 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200'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]) 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
1Elfogadva8ms9820 KiB
2Elfogadva19ms11072 KiB
subtask20/10
3Hibás válasz8ms9928 KiB
4Hibás válasz10ms9780 KiB
5Elfogadva10ms9780 KiB
6Elfogadva9ms9780 KiB
7Hibás válasz8ms9776 KiB
subtask310/10
8Elfogadva8ms9868 KiB
9Elfogadva8ms9780 KiB
10Elfogadva10ms9764 KiB
11Elfogadva12ms10028 KiB
12Elfogadva16ms11264 KiB
subtask410/10
13Elfogadva21ms12908 KiB
14Elfogadva10ms9780 KiB
15Elfogadva10ms9780 KiB
16Elfogadva9ms10036 KiB
17Elfogadva158ms28564 KiB
18Elfogadva56ms14588 KiB
19Elfogadva75ms15784 KiB
20Elfogadva56ms14672 KiB
subtask50/10
21Elfogadva17ms11060 KiB
22Elfogadva8ms9780 KiB
23Hibás válasz10ms9784 KiB
24Elfogadva10ms9780 KiB
25Elfogadva94ms20388 KiB
26Elfogadva17ms10484 KiB
27Elfogadva14ms10576 KiB
subtask60/60
28Elfogadva8ms9780 KiB
29Elfogadva10ms9780 KiB
30Elfogadva13ms10036 KiB
31Elfogadva10ms10036 KiB
32Hibás válasz12ms10348 KiB
33Elfogadva13ms10340 KiB
34Elfogadva19ms10960 KiB
35Elfogadva20ms11164 KiB
36Elfogadva17ms10964 KiB
37Elfogadva151ms28668 KiB
38Elfogadva59ms14656 KiB
39Elfogadva59ms14512 KiB
40Elfogadva54ms14476 KiB
41Elfogadva61ms14500 KiB
42Elfogadva59ms14500 KiB
43Elfogadva56ms14508 KiB
44Elfogadva56ms14576 KiB
45Elfogadva82ms15884 KiB
46Elfogadva61ms14500 KiB
47Elfogadva57ms14480 KiB
48Elfogadva57ms14420 KiB
49Elfogadva54ms14620 KiB
50Elfogadva57ms14516 KiB