dfs _ bfs

存图

// // 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
// int h[N], e[N], ne[N], idx;

// // 添加一条边a->b
// void add(int a, int b)
// {
//     e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
// }

// // 初始化
// idx = 0;
// memset(h, -1, sizeof h);

dfs 树的重心

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'
#define mem(z, o) memset(z, o, sizeof(z))
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define fr(l, ft, ed) for (int l = (ft); l <= (ed); ++l)

const int N = 1e6+10;
int n, h[N], e[N], ne[N], idx;
int vis[N], ans;
inline void add(int u, int v){ e[idx] = v, ne[idx] = h[u], h[u] = idx++; }

// ------------------- 树的重心 -----------------------
int dfs(int u)
{
    int res = 0, sum = 1;
    vis[u] = 1;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!vis[j])
        {
            int t = dfs(j);
            res = max(res, t);
            sum += t;
        }
    }
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}
signed main()
{
    IOS
    mem(h, -1);
    cin >> n;
    fr (i, 1, n-1)
    {
        int a, b; cin >> a >> b;
        add(a, b), add(b, a);
    }
    ans = N;
    dfs(1);
    cout << ans << endl;
    return 0;
}

dfs ------------------------- n 皇后 ---------------------

char g[10][10];
bool lie[10], de[10<<1], ude[10<<1];
int n;

void Dfs(int u)
{
    if (u >= n)
    {
        for (int i = 0; i < n; ++i) puts(g[i]);
        puts("");
        return ;
    }
    for (int i = 0; i < n; ++i)
    {
        if (!lie[i] && !de[u + i] && !ude[n + u - i])
        {
            lie[i] = de[u + i] = ude[n + u - i] = 1;
            g[u][i] = 'Q';
            dfs(u+1);
            lie[i] = de[u + i] = ude[n + u - i] = 0;
            g[u][i] = '.';
        }
    }
}
signed main()
{
    // IOS
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            g[i][j] = '.';
    Dfs(0);
    return 0;
}

-------------------------- Bfs ____ 八数码 ----------------------------------

using pii = pair<int, int>;
int d[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char gg[10];
unordered_map<string, int> mp;

int bfs(string &s)
{
    int z = s.find('x');
    string end = "12345678x";
    queue<string> que;
    que.push(s);
    mp[s] = 0;
    while (!que.empty())
    {
        auto t = que.front(); que.pop();
        int dd = mp[t];
        if (t == end) return dd;
        int k = t.find('x');
        for (int i = 0; i < 4; ++i)
        {
            int a = k / 3 + d[i][0], b = k % 3 + d[i][1];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[k], t[a * 3 + b]);
                if (!mp[t])
                {
                    que.push(t);
                    mp[t] = dd + 1;
                }
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    return -1;
}
signed main()
{
    // IOS
    string s = "";
    for (int i = 0; i < 9; ++i)
            gg[i] = getchar(), getchar(), s += gg[i];
    cout << bfs(s) << endl;
    return 0;
}