【持续更新】做题回顾和总结

2023-08-14 23:11:10 来源：博客园

(资料图)

最近在做树和图相关的题目。中间碰到过很多关于 vis 数组的运用。这里总结一下。

vis 数组分成两种，一种是函数调用前 vis，return 的时候再取消。这样是枚举不同的 dfs 路径，在一个节点下面的所有孩子跑递归。

另外一种是全局 vis， vis 过一遍就不用再vis了。这里注意vis的位置，下面会提到。

对于树上问题，无论是 BFS 还是 DFS，怎么vis都行，无论是全局还是路径搜索。甚至不需要 vis，直接判断是否是父节点，然后 continue 掉就行（注意所有的 continue 之前要重复一边一般的结束条件）。

对于图上问题，要分情况，看是哪一种。注意，DFS 不介意在 kids 那里变 true 还是在递归的开始处。但是 BFS 是有问题的，一般来讲要在 kids 那里就把 vis 变 true，因为放入队列会有延迟处理，本来要被 vis 的没有被判掉。

对于二分图，是多次全局 vis，然后每次清零。不要写成随问随清，因为这样会变成搜索，就挂了。vis 必要的记录是记录右侧（当以左侧为开始）。都记录是可以的。可以不去重边。

无论什么样的 vis，都要结合实际情况和效果，在脑海里面过一遍，或者拿笔画一画，看看是不是自己想要的效果。无论什么问题，都要注意 vis 和其他配套数组的初始化。

优先队列优化的目的是只有一遍。不然复杂度和普通队列无异，毕竟有 vis 配合。

关键词：