求问:tanjan内前++和后++的区别
查看原帖
求问:tanjan内前++和后++的区别
1125645
DyingEncoder楼主2025/7/1 12:29

这行代码dfn[u]=low[u]=++timestamp;为什么一定要把"++"写在前面,在后面就会WA?

//这是一个tarjan的模板
int dfn[N],low[N],timestamp;
bool st[N];
int id[N],size[N],scc_cnt;
int stk[N],top;
void tarjan(int u){
	dfn[u]=low[u]=++timestamp;
	st[u]=1;stk[++top]=u;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(!dfn[j]){
			tarjan(j);
			low[u]=min(low[u],low[j]);
		}else if(st[j]){
			low[u]=min(low[u],dfn[j]);
		}
	}
	
	if(dfn[u]==low[u]){
		scc_cnt++;
		int j;
		do{
			j=stk[top--];
			st[j]=0;
			id[j]=scc_cnt;
			size[scc_cnt]++;
		}while(u!=j);
	}
}
2025/7/1 12:29
加载中...