社区讨论

为什么tajian会重复计算算一个点

P3388【模板】割点(割顶)参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6ufums
此快照首次捕获于
2025/11/20 11:00
4 个月前
此快照最后确认于
2025/11/20 11:00
4 个月前
查看原帖
这是80分代码
CPP
//#include<iostream>
#include<cstdio>
#include<algorithm>

#define fom(i, a, b) for(int i = a; i <= b; i++)
#define foi(i, a, b) for(int i = a; i >= b; i--)
#define MAXN 100010
#define mod 1000000007

int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }

using namespace std;

int read() {
    int ans = 0; char ch = getchar(), t;
    while (ch < '0' || ch > '9') { t = ch; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { ans = ans * 10 + ch - '0'; ch = getchar(); }
    if (t == '-') ans = -ans;
    return ans;
}

int sum, head[MAXN], num, root, dfn[MAXN], low[MAXN], cut[MAXN];
struct node {
    int pre, next;
    inline void add(int x, int y) {
        pre = y;
        next = head[x]; head[x] = sum;
    }
}e[MAXN * 2];

void trjian(int x) {
    dfn[x] = low[x] = ++num;
    int flag = 0;
    for (int i = head[x]; i; i = e[i].next) {
        int u = e[i].pre;
        if (!dfn[u]) {
            trjian(u);
            low[x] = min(low[u], low[x]);
            if (low[u] >= dfn[x]) {
                flag++;
                if (x != root || flag > 1) cut[++sum] = x;//两个代码区别在这里
            }
        }
        else low[x] = min(low[x], dfn[u]);
    }
}

int main() {
    int n = read(), m = read();
    fom(i, 1, m) {
        int x = read(), y = read();
        if (x == y) continue;
        e[++sum].add(x, y); e[++sum].add(y, x);
    }
    sum = 0;
    fom(i, 1, n) if (!dfn[i]) root = i, trjian(i);
    printf("%d\n", sum);
    sort(cut + 1, cut + sum + 1);
    fom(i, 1, sum) printf("%d ", cut[i]);
    return 0;
}
这是100分代码
CPP
//#include<iostream>
#include<cstdio>

#define fom(i, a, b) for(int i = a; i <= b; i++)
#define foi(i, a, b) for(int i = a; i >= b; i--)
#define MAXN 100010
#define mod 1000000007

int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }

using namespace std;

int read() {
    int ans = 0; char ch = getchar(), t;
    while (ch < '0' || ch > '9') { t = ch; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { ans = ans * 10 + ch - '0'; ch = getchar(); }
    if (t == '-') ans = -ans;
    return ans;
}

int sum, head[MAXN], num, root, dfn[MAXN], low[MAXN], cut[MAXN];
struct node {
    int pre, next;
    inline void add(int x, int y) {
        pre = y;
        next = head[x]; head[x] = sum;
    }
}e[MAXN * 2];

void trjian(int x) {
    dfn[x] = low[x] = ++num;
    int flag = 0;
    for (int i = head[x]; i; i = e[i].next) {
        int u = e[i].pre;
        if (!dfn[u]) {
            trjian(u);
            low[x] = min(low[u], low[x]);
            if (low[u] >= dfn[x]) {
                flag++;
                if ((x != root || flag > 1) && cut[x] != 1) cut[x] = 1, ++sum;//两个代码区别在这里
            }
        }
        else low[x] = min(low[x], dfn[u]);
    }
}

int main() {
    int n = read(), m = read();
    fom(i, 1, m) {
        int x = read(), y = read();
        if (x == y) continue;
        e[++sum].add(x, y); e[++sum].add(y, x);
    }
    sum = 0;
    fom(i, 1, n) if (!dfn[i]) root = i, trjian(i);
    printf("%d\n", sum);
    fom(i, 1, n) if (cut[i])printf("%d ", i);
    return 0;
}
求大佬解答

回复

4 条回复,欢迎继续交流。

正在加载回复...