如果你不会使用vector删除反向边
查看原帖
如果你不会使用vector删除反向边
482130
Kx_Triumphs楼主2024/10/6 22:42

题解里貌似都是链式前向星存图,这时肯定有人想用 vectorvector 存图吧?但如果你不会反向边,那可就完蛋了。

那么怎么实现呢?

其实也很简单,只需要在存图的时候同时将边的编号存下来(反向边编号就加 mm ),标记删除时判断当前走的是否是反向边就行了。

  • 存边
void add(int u,int v,int i){//vector
	e[u].push_back({v,i});
}
int main(){
	...
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a,&b,&s,&t);
		if(s==t) continue;
		add(a,b,i);
		add(b,a,i+m);
		dg[a]++;
		dg[b]++;
	}
	...
}
  • 删边
//dfs中调用(rv标记删除的边)
for(int i=0;i<e[x].size();i++){//vector
	int y=e[x][i].first,id=e[x][i].second;
	if(rv[id]) continue;
	rv[id]=1;
  //删除反向边
	if(id<=m) rv[id+m]=1;
	else rv[id-m]=1;
	dfs(y);
}
2024/10/6 22:42
加载中...