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;
}