关于Tarjan
  • 板块灌水区
  • 楼主FChang
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/6/8 21:47
  • 上次更新2024/6/9 08:32:09
查看原帖
关于Tarjan
744853
FChang楼主2024/6/8 21:47
int sc, Time; 
int dfn[N], low[N], SCC[N];
bool vis[N]; 
stack<int> st; 
vector<int> vc[N]; 
inline void Tarjan(int x) {
	dfn[x] = low[x] = ++Time; 
	vis[x] = true; st.push(x); 
	for(intt i=head[x];i;i=a[i].nxt) {
      int it = a[i].to;
		 if(!dfn[it]) {
		 	Tarjan(it);
		 	low[x] = min(low[x], low[it]); 
		 } else if(vis[it]) low[x] = min(low[x], dfn[it]); 
	}
	if(dfn[x] == low[x]) {
		int v = 0; ++sc; 
		do {
			v = st.top(); st.pop(); 
			vis[v] = false; SCC[v] = cnt; 
		} while(v != x); 
	}
	return ; 
}
-------------------------------
for(int i = 1; i <= n; ++i)
  	if(!dfn[i]) Tarjan(i); 

如果一个点没有可以去的点,那么Tarjan算法中的low[x]就直接等于dfn[x]没有任何的修改,就会判环,感觉有问题,没想通

2024/6/8 21:47
加载中...