关于以下两种tarjan写法
bool ins[MAXN];//是否在栈内
inline void tarjan( int x ){
dfn[x] = low[x] = ++_time;
s[++top] = x;
ins[x] = 1;
for( int i = head[x]; i; i = e[i].nxt ){
int y = e[i].v;
if( !dfn[y] ){
tarjan( y );
low[x] = min( low[x], low[y] );
}
else if( ins[y] ) low[x] = min( low[x], dfn[y] );
}
if( dfn[x] == low[x] ){
int y = inf;
tot++;
while( x != y ){
y = s[top--];
ins[y] = 0;
belong[y] = tot;
dis[tot] += val[y];
}
}
}
int belong[MAXN], tot;//SCC编号,总数
inline void tarjan( int x ){
dfn[x] = low[x] = ++_time;
s[++top] = x;
for( int i = head[x]; i; i = e[i].nxt ){
int y = e[i].v;
if( !dfn[y] ){
tarjan( y );
low[x] = min( low[x], low[y] );
}
else if( !belong[y] ) low[x] = min( low[x], dfn[y] );
}
if( dfn[x] == low[x] ){
int y = inf;
tot++;
while( x != y ){
y = s[top--];
belong[y] = tot;
dis[tot] += val[y];
}
}
}
其中
else if( !belong[y] ) low[x] = min( low[x], dfn[y] );
和
else if( ins[y] ) low[x] = min( low[x], dfn[y] );
都可以AC,请问这两种写法有什么区别呢?