社区讨论
这究竟是题目数据的锅还是什么原因
P2863[USACO06JAN] The Cow Prom S参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6yvbxg
- 此快照首次捕获于
- 2025/11/20 13:04 4 个月前
- 此快照最后确认于
- 2025/11/20 13:04 4 个月前
我今天在学Tarjan算法求强连通分量,于是想弄个模板题来连连手。结果书上还有很多博客里面的Tarjan算法在更新
CPPlow 值的时候都是很复杂。但是我的Tarjan函数这么写却A掉了这个题目。所以来问问为什么,这么写究竟是不是对的,要是考试的时候因为这么些WA了就不好了。void Tarjan(int x, int index) {
dfn[x] = low[x] = index;
stack_tmp[++tail] = x;
check[x] = true;
for (register int i = head[x]; i; i = Edge[i].nxt) {
if (!dfn[Edge[i].e]) Tarjan(Edge[i].e, index + 1);
low[x] = Min(low[x], low[Edge[i].e]);
}
if (low[x] == dfn[x]) {
int sum = 0;
while (stack_tmp[tail] != x && tail > 0) {
check[stack_tmp[tail]] = false;
++sum;
--tail;
}
if (tail != 0 && stack_tmp[tail] == x) {
check[stack_tmp[tail]] = false;
++sum;
--tail;
}
if (sum > 1) ++ans;
}
}
下面是这个题目的完整代码:
CPP#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int M = 5e4 + 5;
int n, m;
int u, v;
int head[N];
int cnt = 0;
int ans = 0;
int dfn[N], low[N];
int stack_tmp[N], tail = 0;
bool check[N];
inline int Min(int x, int y) {
return x <= y ? x : y;
}
struct EDGE {
int s;
int e;
int nxt;
} Edge[N];
void add(int u, int v) {
++cnt;
Edge[cnt].s = u;
Edge[cnt].e = v;
Edge[cnt].nxt = head[u];
head[u] = cnt;
}
void Tarjan(int x, int index) {
dfn[x] = low[x] = index;
stack_tmp[++tail] = x;
check[x] = true;
for (register int i = head[x]; i; i = Edge[i].nxt) {
if (!dfn[Edge[i].e]) Tarjan(Edge[i].e, index + 1);
low[x] = Min(low[x], low[Edge[i].e]);
}
if (low[x] == dfn[x]) {
int sum = 0;
while (stack_tmp[tail] != x && tail > 0) {
check[stack_tmp[tail]] = false;
++sum;
--tail;
}
if (tail != 0 && stack_tmp[tail] == x) {
check[stack_tmp[tail]] = false;
++sum;
--tail;
}
if (sum > 1) ++ans;
}
}
int read() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int main(int argc, char const *argv[]) {
n = read(), m = read();
for (register int i = 1; i <= m; ++i) {
u = read(), v = read();
add(u, v);
}
Tarjan(1, 1);
for (register int i = 1; i <= n; ++i)
if (!dfn[i]) Tarjan(i, 1);
write(ans), putchar('\n');
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...