更玄学的问题玄关求条
查看原帖
更玄学的问题玄关求条
636977
CC__DIAMOND楼主2024/6/1 14:44

rt.这回能够正常运行了,但是WA了很多点。下下来数据在我本地测试答案是对的,但是在锣鼓上就是过不去。代码里应该没有UB.是不是有什么和环境相关的运行时错误?

#include <bits/stdc++.h>

#define fst first
#define snd second
#define INFILE(x) freopen(x, "r", stdin)
#define OUTFILE(x) freopen(x, "w", stdout);

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

constexpr int max_n = 2e4 + 10;

vector<int> graph[max_n], cut;
int id = 0, dfn[max_n], low[max_n];
bool vis[max_n];

void dfs(int s, int from) {
    low[s] = dfn[s] = ++id;
    vis[s] = true;
    int cnt = 0;
    for (int od: graph[s]) {
        if (od == from) continue;
        if (vis[od]) {
            low[s] = min(low[s], dfn[od]);
            continue;
        }
        dfs(od, s);
        low[s] = min(low[s], low[od]);
        if (low[od] >= dfn[s]) ++cnt;
    }
    if ((from && cnt) || cnt >= 2) {
        cut.emplace_back(s);
    }
}

int main() {
    INFILE("P3388_1.in");
    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(v);
        graph[v].emplace_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) dfs(i, 0);
    }
    sort(cut.begin(), cut.end());
    cout << cut.size() << '\n';
    for (int c: cut) cout << c << ' ';
    cout << '\n';
    return 0;
}

2024/6/1 14:44
加载中...