codetop图论篇

DFS一些经典题目

acwing 842. 排列数字

给定一个整数 n，将数字 1∼n 排成一排，全排列数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>

using namespace std;

const int N = 10;

int n, path[N];
bool st[N];

void dfs(int u)
{
    if (u == n)
    {
        // 输出保存的结果
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        puts("");
    }
    
    for (int i = 1; i <= n; i ++ )
    	if (!st[i]) // 没有用过的数
        {
            path[u] = i;
            st[i] = true;  // i被用过
            dfs(u + 1);  // 走到下一层
            st[i] = false;  //恢复现场
        }
}

int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

acwing 843. n-皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 解法 一
#include <iostream>

using namespace std;

const int N = 10;

int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];
char g[N][N];

void dfs(int x, int y, int s)
{
    if (s > n) return ;
    if (y == n) y = 0 , x ++ ;
    
    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return ;
    }
    
    g[x][y] = '.';
    dfs(x, y + 1, s);
    
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main()
{
    cin >> n;
    
    dfs(0, 0, 0);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 解法 二
#include <iostream>
using namespace std;

int n;
const int N = 20;
bool col[N], dg[N], udg[N];
char g[N][N];

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
    }
    
    for (int i = 0; i < n; i ++ )
        if (!col[i] && !dg[u + i] && !udg[u - i + n])
        {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[u - i + n] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[u - i + n] = false;
            g[u][i] = '.';
        }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';
    
    dfs(0);
    
    return 0;
}

解法二的思想就是在每一行放皇后，这是控制了行

BFS一些题目

AcWing 844 走迷宫

最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 110;
int n, m, g[N][N], d[N][N];

int bfs()
{
    queue<PII> q;
    
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    
    return d[n - 1][m - 1];
}


int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            scanf("%d", &g[i][j]);
    cout << bfs() << endl;
    
    return 0;
}

AcWing 845 八数码

1
2
3
4
1 2 3
x 4 6
7 5 8
// 最后要得到 12345678x  这个字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;

int bfs(string state)
{
    queue<string> q;
    unordered_map<string, int> d;
    
    q.push(state);
    d[state] = 0;
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    string end = "12345678x";
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        if (t == end) return d[t];
        
        int distance = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[a * 3 + b], t[k]);
                if (!d.count(t))
                {
                    q.push(t);
                    d[t] = distance + 1;
                }
                swap(t[a * 3 + b], t[k]);
            }
        }
    }
    return -1;
}

int main()
{
    char s[2];
    string state;
    
    for (int i = 0; i < 9; i ++ )
    {
        cin >> s;
        state += *s;
    }
    
    cout << bfs(state) << endl;
    
    return 0;
}

树与图的深度优先遍历

acwing 845.树的重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = N * 2;
int h[N], e[M], ne[M], idx;
int n, ans = N;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u)
{
    st[u] = true;
    
    int size = 0, sum = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;
        
        int s= dfs(j);
        size = max(size, s);
        sum += s;
    }
    size = max(size, n - sum - 1);
    ans = min(ans, size);
    
    return sum + 1;
}

int main()
{
    scanf("%d", &n);
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b,a );
    }
    
    dfs(1);
    
    cout << ans << endl;
    
    return 0;
}

做一个说明，h[i]表示i的头节点索引；e[idx]是当前边指向的节点，ne[idx]是下一个邻接边的索引；idx是边的编号

1
2
3
4
5
6
7
8
9
10
11
12
// 这部分需要理解一下
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
假设 add(1,2)
e[0] = 2, ne[0] = -1, h[1] = 0
h[1] --> idx:0 --> b:2, ne:-1     // 就是这种样子的

add(1,3) 
e[1] = 3, ne[1] = h[1], h[1] = 1
h[1] --> idx:1 --> 3 ---- idx:1 ---- > 2, ne:-1     // 就是这种样子的

数与图的广度优先遍历

AcWing 847.图中点的层次