为什么树的dfs不需要vis数组,只需要维护父节点就可以?
title: 为什么树的dfs不需要vis数组,只需要维护父节点就可以?
categories:
- ICPC
tags:
- null
abbrlink: 572bc114
date: 2023-03-12 00:00:00
无向图无环的,无环的图总是可以展成树的形式。
然后考虑无向图,顶多有回边指向父节点。不可能有回边指向祖先。更不可能有横向边,因为无环啊。所以只需要考虑指向父节点的回边就可以无需使用Vis。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!