请问求边双、强联通分量为什么 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[],应该前面的不影响才对吧?
望解答。(可能我现在有点脑残)