tarjan65分求助(qq啦
查看原帖
tarjan65分求助(qq啦
373959
AFwhcing楼主2021/12/22 21:21

不知咋搞的,测试点红红绿绿啊 这个在图死了的时候出现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int b, e;
int dfn[100010], low[100010], _index;
int vis[100010], stk[100010];
int belong[100010], need[100010];
int tot, ans;
stack<int> s;
vector<int> g[100010];

void tarjan(int u) {
	dfn[u] = low[u] == ++_index;
	s.push(u);
	vis[u] = stk[u] = 1;
	int sum = g[u].size();
	for (int i = 0; i < sum; ++i) {
		int v = g[u][i];
		if (!vis[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else {
			if (stk[v]) {
				low[u] = min(low[u], dfn[v]);
			}
		}
	}
	if (dfn[u] == low[u]) {
		int v;
		tot++;
		do {
			v = s.top();
			stk[v] = 0;
			belong[v] = tot;
			s.pop();
		} while (v != u);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &b, &e);
		g[b].push_back(e);
	}
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			tarjan(i);
		}
	}
	for (int i = 1; i <= n; ++i) {
		int sum = g[i].size();
		for (int j = 0; j < sum; ++j) {
			int x = g[i][j];
			if (belong[i] != belong[x]) {
				need[belong[x]] = 1;
			}
		}
	}
	for (int i = 1; i <= tot; ++i) {
		if (!need[i]) {
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

没有A这题的蒟蒻,或者还有?

救救蒟蒻……

2021/12/22 21:21
加载中...