题解里貌似都是链式前向星存图,这时肯定有人想用 vector 存图吧?但如果你不会删反向边,那可就完蛋了。
那么怎么实现呢?
其实也很简单,只需要在存图的时候同时将边的编号存下来(反向边编号就加 m ),标记删除时判断当前走的是否是反向边就行了。
void add(int u,int v,int i){
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]++;
}
...
}
for(int i=0;i<e[x].size();i++){
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);
}