奇葩错误玄关求条
查看原帖
奇葩错误玄关求条
636977
CC__DIAMOND楼主2024/6/1 11:07

rt.出现的问题莫名其妙。按理说程序占用内存不到900kb(拿锣鼓ide测样例的确如此),交上去全部MLE。下载数据本地自测发现25行出现段错误。然而graph数组并未越界。

#include <bits/stdc++.h>

#include <cassert>
#include <vector>
#define fst first
#define snd second

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

constexpr int max_n = 2e4 + 10;

vector<pii> graph[max_n];
vector<int> cut_vers;
int dfn[max_n], low[max_n];
bool vis[max_n];

void dfs(int s, int from, int j) {
    low[s] = dfn[s] = j;
    vis[s] = true;
    int cnt = 0;
    assert(s < max_n);
    for (auto &e : graph[s]) {
        if (e.fst == from) continue;
        if (vis[e.fst]) {
            low[s] = min(low[s], dfn[e.fst]);
            continue;
        }
        dfs(e.snd, e.fst, ++j);
        low[s] = min(low[s], low[e.snd]);
        if (low[e.snd] >= dfn[s]) ++cnt;
    }
    if (from && cnt) {
        cut_vers.emplace_back(s);
    } else if (!from && cnt >= 2) {
        cut_vers.emplace_back(s);
    }
}

int main() {
    freopen("P3388_1.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(i, v);
        graph[v].emplace_back(i, u);
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) dfs(i, 0, 1);
    }
    sort(cut_vers.begin(), cut_vers.end());
    cout << cut_vers.size() << '\n';
    for (int i : cut_vers) cout << i << ' ';
    cout << '\n';
    return 0;
}

2024/6/1 11:07
加载中...