复习

• AcWing 1242. 修改数组（周一）
• AcWing 1234. 倍数问题（周二）
• AcWing 1171. 距离（周三）

前言

害，周二周三的题其实对我来说都太难了。感觉现在学习有点递归算法的感觉，就是学一个发现另外的东西不会。今天写一个 dfs 的模板题好了，明天再写一个 dfs 的模板题，下周再学一下 tarjan 算法。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e5+10;
int p[N];
int find(int x){if(x!=p[x]){p[x]=find(p[x]);}return p[x];
}
int main(){int n;cin>>n;for(int i=1;i<N;i++){p[i]=i;}for(int i=1;i<=n;i++){int x;cin>>x;x=find(x);cout<<x<<" ";p[x]=x+1;}return 0;
}

周二那个题，还有昨天的题确实太难了，等一个好天气，我有足够的时间和勇气的时候再去写那个题。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;
void dfs(int u){if(u==n){for(int i=0;i<n;i++){cout<<path[i]<<" ";}puts("");return ;}for(int i=1;i<=n;i++){if(!st[i]){path[u]=i;st[i]=true;dfs(u+1);path[u]=0;st[i]=false;}}
}
int main(){cin>>n;dfs(0);return 0;
}

思路

排列数字感觉需要注意的点就是，路径存的下标是从 0 开始的，然后数字是从 1 开始计算的，恢复现场是在递归结束之后，回溯之前，这样子可以保证前面的搜索不会影响下一次搜索。搜索树最开始是有 n+1 层，我们从根节点，第 0 层开始搜索，一直搜索到最下面那层结束，然后回溯。深搜，或者叫暴搜，是一条路径走到底再考虑其他路径。