求助
  • 板块学术版
  • 楼主qzilr
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/10/16 15:44
  • 上次更新2023/11/4 03:38:04
查看原帖
求助
400333
qzilr楼主2021/10/16 15:44

Trajan求强连通分量,不知道哪里错了

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 5;

struct tree {
	int v, next;
}t[maxn];
int head[maxn], tot = 0, dfn[maxn], low[maxn], instack[maxn], sum = 0, colour[maxn], index = 0;
stack<int> s;

inline void add(int u, int v) {
	t[++tot] = (tree) {v, head[u]};
	head[u] = tot;
}

void Trajan(int o) {
	dfn[o] = low[o] = ++tot;
	instack[o] = 1;
	s.push(o);
	for (int i = head[o]; i; i = t[i].next ) {
		int v = t[i].v ;
		if (!dfn[v]) {
			Trajan(v);
			low[o] = min(low[o], low[v]);
		}
		else {
			if (instack[v]) {
				low[o] = min(low[o], low[v]);
			}
		}
		if (dfn[o] == low[o]) {
			colour[o] = ++index;
			instack[o] = 0;
			while (s.top() != o) {
				instack[s.top()] = 0;
				colour[s.top()] = index;
				s.pop();
			}
			s.pop();
		}
	}
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		add(u, v);
	}
	for (int i = 1; i <= n; ++i)
		if (!dfn[i])
			tot = 0, Trajan(i);
	for (int i = 1; i <= n; ++i)
		printf("%d ", colour[i]);
	return 0;
}
2021/10/16 15:44
加载中...