问个脑残问题
  • 板块学术版
  • 楼主pengyule
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/4/9 14:59
  • 上次更新2023/10/28 04:11:53
查看原帖
问个脑残问题
300078
pengyule楼主2022/4/9 14:59

请问求边双、强联通分量为什么 bel[] 都要每次清零呢?之前打割点的时候就是改了这个地方就过了,现在求边双又是这里有问题。

struct Graph {
	vector<int>G[N],T[N];
	int dfc,tp,cnt,dfn[N],low[N],stk[N],bel[N];
	vector<pair<int,int> >cut_e;
	inline void cl(){dfc=tp=cnt=0;cut_e.clear();}
	void Tarjan(int x,int p){
		dfn[x]=low[x]=++dfc,stk[++tp]=x;
		for(int i=0;i<G[x].size();i++){
			int y=G[x][i];
			if(y^p){
				if(!dfn[y]){
					Tarjan(y,x);
					low[x]=min(low[x],low[y]);
				}
				else low[x]=min(low[x],dfn[y]);
			}
		}
		if(dfn[x]==low[x]){
			cnt++;
			while(tp){
				bel[stk[tp]]=cnt;
				if(stk[tp--]==x)break;
			}
			if(p)cut_e.push_back(make_pair(p,x));
		}
	}
}init,now;

按道理说,上面代码中的 cl() 应该就够了啊……因为每次对所有点分配 bel[],应该前面的不影响才对吧?

望解答。(可能我现在有点脑残)

2022/4/9 14:59
加载中...