已知代码只有此段有问题
void sch(int p){
aiss[p]=true;
iss[p]=true;
for(int i=0;i<l[p].size();i++){
if(!aiss[l[p][i]]){
dfn[l[p][i]]=dfn[p]+1;
low[l[p][i]]=dfn[l[p][i]];
bl[l[p][i]]=l[p][i];
sch(l[p][i]);
}
if(low[l[p][i]]<low[p] && iss[getbl(l[p][i])]){
low[p]=low[l[p][i]];
bl[p]=bl[l[p][i]];
}
}
iss[p]=false;
return;
}
本段代码类似tarjan,dfn表示深度,low含义一样,bl为能回到的深度最小的点的编号。
每搜到一个点就打上aiss和iss标记,退出时取消iss标记,可以借此判断是否被搜过以及是否在本次搜索的栈中(其实我没有栈)。
对于搜索过的点,如果它能回到的深度最小的点在栈中便更新low和bl。如果没有搜索过就搜索。
已用tarjan过此题,但不知道为何之前用的这个方法过不了#7,故求助。