162692025-04-19 10:39:18szilTurista járatokcpp17Hibás válasz 20/100162ms42716 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]) 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
1Elfogadva24ms23860 KiB
2Elfogadva28ms25140 KiB
subtask20/10
3Hibás válasz25ms23860 KiB
4Hibás válasz25ms23800 KiB
5Elfogadva19ms23860 KiB
6Elfogadva19ms24052 KiB
7Hibás válasz23ms23740 KiB
subtask310/10
8Elfogadva24ms24076 KiB
9Elfogadva25ms23860 KiB
10Elfogadva19ms23860 KiB
11Elfogadva20ms24116 KiB
12Elfogadva25ms25300 KiB
subtask410/10
13Elfogadva39ms27116 KiB
14Elfogadva19ms23812 KiB
15Elfogadva25ms23860 KiB
16Elfogadva20ms24116 KiB
17Elfogadva157ms42716 KiB
18Elfogadva65ms28616 KiB
19Elfogadva92ms29968 KiB
20Elfogadva75ms28584 KiB
subtask50/10
21Elfogadva35ms25140 KiB
22Elfogadva19ms23860 KiB
23Hibás válasz19ms23860 KiB
24Elfogadva25ms23952 KiB
25Elfogadva108ms34464 KiB
26Elfogadva26ms24628 KiB
27Elfogadva26ms24628 KiB
subtask60/60
28Elfogadva20ms23860 KiB
29Elfogadva20ms23860 KiB
30Elfogadva21ms24080 KiB
31Elfogadva27ms24116 KiB
32Hibás válasz28ms24240 KiB
33Elfogadva25ms24388 KiB
34Elfogadva28ms25248 KiB
35Elfogadva35ms25300 KiB
36Elfogadva34ms25136 KiB
37Elfogadva162ms42648 KiB
38Elfogadva75ms28740 KiB
39Elfogadva65ms28704 KiB
40Elfogadva72ms28840 KiB
41Elfogadva75ms28580 KiB
42Elfogadva68ms28580 KiB
43Elfogadva67ms28576 KiB
44Elfogadva74ms28580 KiB
45Elfogadva96ms29932 KiB
46Elfogadva68ms28628 KiB
47Elfogadva68ms28584 KiB
48Elfogadva75ms28580 KiB
49Elfogadva65ms28660 KiB
50Elfogadva72ms28596 KiB