DFS

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走
DFS 最显著的特征在于其 递归调用自身。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次。符合以上两条规则的函数，便是广义上的 DFS

全排列
  1. const int N = 110;
  2. int n,a[N];
  3. bool st[N];
  4. void dfs(int u) {
  5.     if (u == n) {
  6.         for(int i = 0; i < n; i ++ ) {
  7.             cout << a[i] << ' ';
  8.         }
  9.         cout << endl;
  10.         return;
  11.     }
  12.     for (int i = 1; i <= n; i ++ ) {
  13.         if(!st[i]) {
  14.             st[i] = true;
  15.             a[u] = i;
  16.             dfs(u + 1);
  17.             st[i] = false;
  18.         }
  19.     }
  20. }
  21. int main()
  22. {
  23.     cin >> n;
  24.     dfs(0);
  25.     return 0;
  26. }

八皇后
  1. const int N = 110;
  2. char a[N][N];
  3. int n;
  4. bool col[N],dg[N],udg[N];
  6. void dfs(int u) {
  7.     if (u == n) {
  8.         for(int i = 0; i < n; i ++ ) {
  9.             puts(a[i]);
  10.         }
  11.         cout << endl;
  12.         return;
  13.     }
  14.     for (int i = 0; i < n; i ++ ) {
  15.         if(!col[i] and !dg[u + i] and !udg[n - u + i]) {
  16.             col[i] = dg[u + i] = udg[n - u + i] = true;
  17.             a[u][i] = 'Q';
  18.             dfs(u + 1);
  19.             a[u][i] = '.';
  20.             col[i] = dg[u + i] = udg[n - u + i] = false;
  21.         }
  22.     }
  23. }
  25. int main()
  26. {
  27.     cin >> n;
  28.     for (int i = 0; i < n; i ++ ) {
  29.         for (int j = 0; j < n; j ++ ) {
  30.             a[i][j] = '.';
  31.         }
  32.     }
  33.     dfs(0);
  34.     return 0;
  35. }

有向图的拓扑序列
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 100010;
  4. int h[N],e[N],ne[N],d[N],idx,n,m,a,b;
  5. vector<int> ans;
  7. void add(int a,int b) {
  8.     e[idx] = b;
  9.     ne[idx] = h[a];
  10.     h[a] = idx++;
  11. }
  13. bool topsort() {
  14.     queue<int> q;
  15.     for(int i = 1;i<=n;i++){
  16.         if(!d[i]) q.push(i);
  17.     }
  18.     while(!q.empty()) {
  19.         int t = q.front();
  20.         q.pop();
  21.         ans.push_back(t);
  22.         for(int i = h[t];i!=-1;i = ne[i]){
  23.             int j = e[i];
  24.             if(--d[j]==0) q.push(j);
  25.         }
  26.     }
  27.     return ans.size()==n;
  28. }
  31. int main()
  32. {
  33.     cin >> n >> m;
  34.     memset(h, -1, sizeof h);
  35.     while(m -- ) {
  36.         cin >> a >> b;
  37.         add(a, b);
  38.         d[b] ++;
  39.     }
  40.     if(topsort()) {
  41.         for(int i = 0;i<n;i++) {
  42.             cout << ans[i] << " ";
  43.         }
  44.     }else{
  45.         cout << -1 << endl;
  46.     }
  47.     return 0;
  48. }

图中点的层次
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1000010;
  4. int h[N],e[N],ne[N],d[N],idx,n,m,a,b;
  6. void add(int a,int b) {
  7.     e[idx] = b;
  8.     ne[idx] = h[a];
  9.     h[a] = idx++;
  10. }
  13. int bfs()
  14. {
  15.     queue<int> q;
  16.     q.push(1);
  17.     memset(d,-1,sizeof d);
  18.     d[1] = 0;
  19.     while(!q.empty()) {
  20.         int t = q.front();
  21.         q.pop();
  22.         for(int i = h[t];i!=-1;i = ne[i]) {
  23.             int j = e[i];
  24.             if(d[j]==-1){
  25.                 d[j] = d[t] + 1;
  26.                 q.push(j);
  27.             }
  28.         }
  29.     }
  30.     return d[n];
  31. }
  34. int main()
  35. {
  36.     cin >> n >> m;
  37.     memset(h, -1, sizeof h);
  38.     while(m -- ) {
  39.         cin >> a >> b;
  40.         add(a, b);
  41.     }
  42.     cout << bfs() << endl;
  43.     return 0;
  44. }

树的重心
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 200020;
  4. int h[N],e[N],ne[N],n,idx,a,b;
  5. bool st[N];
  6. int ans = N;
  7. void add(int a,int b) {
  8.     e[idx] = b;
  9.     ne[idx] = h[a];
  10.     h[a] = idx++;
  11. }
  13. int dfs(int u) {
  14.     st[u] = true;
  15.     int sum = 1,res = 0;
  16.     for(int i = h[u];i!=-1;i=ne[i]) {
  17.         int j = e[i];
  18.         if(!st[j]){
  19.             int s = dfs(j);
  20.             res = max(res,s);
  21.             sum += s;
  22.         }
  23.     }
  24.     res = max(res,n-sum);
  25.     ans = min(ans,res);
  26.     return sum;
  27. }
  29. int main()
  30. {
  31.     cin >> n;
  32.     memset(h, -1, sizeof h);
  33.     for(int i = 1;i<n;i++) {
  34.         cin >> a >> b;
  35.         add(a,b),add(b,a);
  36.     }
  37.     dfs(n);
  38.     cout << ans << endl;
  39.     return 0;
  40. }

八数码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. string s,res = "12345678x";
  4. int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
  6. int bfs() {
  7.     queue<string> q;
  8.     q.push(s);
  9.     unordered_map<string,int> d;
  10.     d[s] = 0;
  11.     while(!q.empty()) {
  12.         auto t = q.front();
  13.         q.pop();
  14.         int x = t.find('x');
  15.         int distance = d[t];
  16.         if(t==res) return distance;
  17.         for(int i = 0;i<4;i++){
  18.             int a = x/3+dx[i] , b = x%3+dy[i];
  19.             if(a>=0 and a<3 and b>=0 and b<3){
  20.                 swap(t[x],t[3*a+b]);
  21.                 if(!d.count(t)){
  22.                     d[t] = distance + 1;
  23.                     q.push(t);
  24.                 }
  25.                 swap(t[x],t[3*a+b]);
  26.             }
  27.         }
  28.     }
  29.     return -1;
  30. }
  32. int main()
  33. {
  34.     char ch;
  35.     for(int i = 0;i<9;i++) {
  36.         cin >> ch;
  37.         s += ch;
  38.     }
  39.     cout << bfs() << endl;
  40.     return 0;
  41. }