社区讨论
关于此题的一些疑问(没有代码求调
P3387【模板】缩点参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo88mlhr
- 此快照首次捕获于
- 2023/10/27 14:34 2 年前
- 此快照最后确认于
- 2023/10/27 14:34 2 年前
关于以下两种tarjan写法
CPPbool 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];
}
}
}
CPP
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,请问这两种写法有什么区别呢?回复
共 3 条回复,欢迎继续交流。
正在加载回复...