蒟蒻自写,递归出问题了,麻烦大佬帮我改一下,必关!!!
查看原帖
蒟蒻自写,递归出问题了,麻烦大佬帮我改一下,必关!!!
1377407
lylin123楼主2024/8/5 12:09
#include <bits/stdc++.h>
using namespace std;
int n, ans, cnt, dfn[25000], low[25000], dfs, cha[25000], in[205];
stack<int> sta;
bool sta_in[25000];

struct Edge {
	int to, next;
} e[25000];
int head[205];

struct Edge_ {
	int to, next;
} rebuild_e[25000];
int rebuild_head[205];

void tarjan(int x, int fa) {
	dfn[x] = low[x] = ++dfs;
	sta.push(x);
	sta_in[x] = 1;
	for (int i = head[x]; i != 0; i = e[i].next) {
		int nxt = e[i].to;
		if (nxt == fa) {
			continue;
		}
		if (!dfn[nxt]) {
			tarjan(nxt, x);
			low[x] = min(low[x], low[nxt]);
		} else if (sta_in[nxt]) {
			do {
				int top = sta.top();
				sta.pop();
				low[top] = min(low[top], dfn[nxt]);
			} while (sta.top() != nxt);
		}
	}
}

void input(int a, int b) {
	e[++cnt].to = b;
	e[cnt].next = head[a];
	head[a] = cnt;
}

void rebuild(int x) {
	for (int i = head[x]; i != 0; i = e[i].next) {
		in[low[e[i].to]]++;
		rebuild_e[++cnt].to = low[e[i].to];
		rebuild_e[cnt].next = rebuild_head[low[i]];
		rebuild_head[low[i]] = cnt;
	}
}

int main() {
	cin >> n;
	int x;
	for (int i = 1; i <= n; i++) {
		while (true) {
			cin >> x;
			if (x == 0) {
				break;
			}
			input(i, x);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i, 0);
		}
	}
	cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (!head[i]) {
			rebuild(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (rebuild_head[i] != 0 && in[i] == 0) {
			ans++;
		}
	}
	cout << ans;
	return 0;
}

2024/8/5 12:09
加载中...