社区讨论

这究竟是题目数据的锅还是什么原因

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算法在更新 low 值的时候都是很复杂。但是我的Tarjan函数这么写却A掉了这个题目。所以来问问为什么,这么写究竟是不是对的,要是考试的时候因为这么些WA了就不好了。
CPP
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 条回复,欢迎继续交流。

正在加载回复...