社区讨论
为什么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 条回复,欢迎继续交流。
正在加载回复...