WA on #7 求调
查看原帖
WA on #7 求调
465032
Last_Flame楼主2023/8/12 07:30

已知代码只有此段有问题

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,故求助。

2023/8/12 07:30
加载中...