2.递归：搜索算法和分治算法
1.1 深度优先搜索
深度优先搜索，一般指通过递归达成“不撞南墙不回头”的搜索。
一般可以用来解决连通块问题、树形dp问题、或者搜索一些状压枚举解决不了的问题。
这里介绍两类深度优先搜索遍历图的代码：
| vector<int>g[100010]; //已经存好的图。图的vector存储方式见stl篇 void dfs(int x,int pr){ //无根树的遍历。x指遍历到的节点，pr指上一个节点。 int i; for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){ dfs(g[x][i],x); //你要进行的操作。 } } //也可以有返回值，适用树形dp。 } |
| vector<int>g[100010]; //已经存好的图。图的vecto |
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
算法笔面试宝典 文章被收录于专栏
算法笔面试真题解析
投递快手等公司10个岗位