2.2.1 DFS中的连通性和搜索顺序

DFS

优先往深度扩展，到叶节点再回溯。由于需要回溯，所以通过栈来实现。一般可以使用系统栈，直接递归搜索。

DFS代码简单，但存在爆栈风险。递归的层数越深，需要的栈空间越大。因而有深度限制，过深会有爆栈问题。栈空间默认为1M，要自己估计是否爆栈。如果爆栈的话需要用迭代的方式来写，将递归改成非递归。

两大类

  1. 内部搜索-空间路径搜索：图的内部从一个点到另一个点的搜索过程，每个点是图的一个具体元素。即棋盘内部从一个棋子到另一个棋子。题目本身就提供具有多个节点的图，搜索的节点间的路径。

  2. 外部搜索-状态图搜索：把整体的当前状态看成一个点，搜索的过程是整体状态变化的过程，由一个状态变换成另一个状态。即棋盘整体布局的变化，从一种棋盘到另一种棋盘。将状态视为节点，初始时只有一个节点，图是在搜索时逐渐构成的，为状态图。

判断回溯时是否需要恢复现场：先DFS再改变当前状态不需要恢复现场，先改变当前状态再DFS则需要恢复现场。

通常内部搜索时，当一个状态向另外一个状态拓展，这个状态是不会变化的。每个状态只搜索一次，所以不需要回溯。

每个节点只搜索一次，所以不能恢复现场，否则会重复搜索。

而外部搜索时通常需要回溯并恢复现场，因为当前状态在递归后会发生改变——因为我们搜索的就是状态转换图。状态本身是节点，要回溯到原节点就要恢复原状态。

不改变节点状态就不需要恢复现场，回溯时需要用到原节点的状态就要恢复现场。

不恢复现场意味着系统帮我们来维护结点状态, 恢复现场意味着自己来维护结点的状态自己维护结点状态指的是搜索一个结点 u 的所有邻接点 v 的时候, 点 u 是固定的, 不能变化的, 这是显而易见的

一. DFS之连通性模型

  1. Flood Fill 模型

  2. 图和树的遍历

连通性模型判断能否连通可以用DFS，也可以用BFS。DFS代码更简单（使用系统栈），但不好处理最短路问题，BFS代码复杂些，但可以求出最短路问题。因此当只用判断连通性时，可以用DFS。

1. AcWing 1112. 迷宫

注意起点和终点是障碍物的话也无法到达

C++

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
58
59
60
// DFS之连通性模型——AcWing 1112. 迷宫 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 105;

int k, n;
int xa, ya, xb, yb;
char g[N][N];
bool st[N][N];

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool dfs(int x, int y){
    // 递归中，首先写出边界条件的判断
    if (g[x][y] == '#') return false; // 即使是终点和起点，如果为'#'，也是不连通
    // 注意判断可以放在递归后最开始时，也可以放在递归前。要结合题目初始和最终条件进行选择
    // 但不要两处都进行判断
    if (x == xb && y == yb) return true;
    
    st[x][y] = true;
    // 不同于bfs，不要在递归后再写一遍，会重复
    // g[x][y] = '#'; // 直接通过改变状态进行标记

    // 枚举所有可移动方向
    for (int i = 0; i < 4; ++ i){
        int a = x + dx[i], b = y + dy[i];
        // 判断不能递归的条件，注意不要和递归后最开始的判断重复
        if (a < 0 || a >= n || b < 0 || b >= n) continue;
        if (st[a][b]) continue; 
        // 进行递归
        if (dfs(a, b)) return true;
        // 递归时如何合理编写返回值、传递要求解的值是一个小难点
        // 这里不能直接return dfs(a, b)
        // 因为当dfs(a, b)为false时，还要继续枚举其他方向
		
        // 递归后一定要判断是否需要回溯和恢复现场
        // 这里不需要恢复现场，属于内部搜索，拓展时不会改变当前状态
    } 
    return false;
}

int main(){
    scanf("%d", &k);
    
    while (k --){
        scanf("%d", &n);
        for (int i = 0; i < n; ++ i) scanf("%s", g[i]);
        scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
        memset(st, 0, sizeof st);
        // 不同于bfs，dfs一定要定义形参，而不是使用全局变量，方便递归
        if (dfs(xa, ya)) puts("YES");
        else puts("NO");
    }
    return 0;
}

python

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
# DFS之连通性模型——AcWing 1112. 迷宫 
from sys import setrecursionlimit
def main():
    T = int(input())
    setrecursionlimit(5000)
    # Python中系统栈默认的递归深度限制为1000，
    # 一般最大可修改到10^5，再大的话可能就需要手写栈等策略
    
    def dfs(x, y):
        if x < 0 or x >= n or y < 0 or y >= n or arr[x][y] == '#' or vis[x][y]:
            return False
        if (x, y) == (ex, ey):
            return True
        vis[x][y] = True # 更新判重
        return dfs(x - 1, y) or dfs(x + 1, y) or dfs(x, y - 1) or dfs(x, y + 1) # 遍历子节点，这里不需要回溯恢复现场所以可以直接这么xie
        
    for _ in range(T):
        n = int(input())
        arr = [input() for _ in range(n)]
        vis = [[False] * n for _ in range(n)]
        sx, sy, ex, ey = map(int, input().split())
        print("YES" if dfs(sx, sy) else "NO")
        
if __name__ == "__main__":
    main()

2. AcWing 1113. 红与黑

C++

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
58
// DFS之连通性模型——AcWing 1113. 红与黑
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 25;

int n, m;
char g[N][N];
bool st[N][N];

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dfs(int x, int y){
    int cnt = 1; 
    // 只算当前点的话个数为1，不是0
    
    st[x][y] = true;
    // 这里递归进入后再进行标记

    for (int i = 0; i < 4; ++ i){
        int a = x + dx[i], b = y + dy[i];
        // 判断能否进入递归
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b]) continue;
        if (g[a][b] != '.') continue;
        
        // 注意dfs中一个注意点是如何在递归中统计要求的量
        // 这里的思路是只统计以当前点为起点的数量，并进行前传，而不用把前面的个数传到后面
        // 这是由于这里求的是所有方案数，前面的点有多种选择，不方便后传（递归时还没统计完），需要递归后才能确定方案数
        // 所以采用递归后前传的方式，分解成子问题，每次递归后统计当前点为起点的方案数
        cnt += dfs(a, b);
    }
    return cnt;
}

int main(){
    // n || m：读入两个零时结束
    // 注意这里先输入列数，再输入行数
    while(scanf("%d%d", &m, &n), n || m){
        int sx, sy;
        for (int i = 0; i < n; ++ i) scanf("%s", g[i]);
        
        for (int i = 0; i < n; ++ i)
            for (int j = 0; j < m; ++ j)
                if (g[i][j] == '@')
                    sx = i, sy = j;
                    // 找到起始点
        
        // 初始化
        memset(st, 0 ,sizeof st);
        printf("%d\n", dfs(sx, sy));
    }
    return 0;
}

python

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
# DFS之连通性模型——AcWing 1113. 红与黑
from sys import setrecursionlimit

def main():
    setrecursionlimit(5000)
    
    def dfs(x, y):
        if x < 0 or x >= n or y < 0 or y >= m or vis[x][y]:
            return 0
        if g[x][y] == '#':
            return 0
        vis[x][y] = True
        return dfs(x - 1, y) + dfs(x + 1, y) + dfs(x, y - 1) + dfs(x, y + 1) + 1
        # 注意不要忘了加1
        # 注意不需要回溯时才能用这种尾递归
        
    # 注意读取输入的方法
    while True:
        m, n = map(int, input().split())
        # 注意审题，行在先还是列在先
        if not (n + m):
            break
        g = [list(input()) for _ in range(n)]
        vis = [[False] * m for _ in range(n)]
        # 使用next获得起点位置
        # next()方法从迭代器中检索下一个项目
        sx, sy = next((x, y) for x in range(n) for y in range(m) if g[x][y] == '@')
        print(dfs(sx, sy))
    
if __name__ == "__main__":
    main()

二. DFS之搜索顺序

外部搜索即通常所说的暴搜问题，需要想一个搜索顺序，使所有方案全部枚举到。

问题可以询问方案数、最优解等。

要想到用怎样的顺序才能不重复、不遗漏地枚举到所有方案/状态。搜索的核心即搜索顺序。

思考时可以结合深度搜索树辅助分析

1. AcWing 1116. 马走日

这里枚举表示马移动的八个方向即可

日字形移动：

dx = {-2, -1, 1, 2, -2, -1, 1, 2}
dy = {-1, -2, -2 ,-1, 1, 2, 2, 1}

注意使用相对变化量，枚举八个位置

因为马的位置状态发生了改变，所以回溯时需要恢复现场。

每一种走法都对应于从根节点到叶子节点的遍历过程，不同的分支代表不同的方案。搜索树上的遍历过程和方案一一对应。

外部搜索是状态图的搜索，每个状态都对应于一个节点

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// DFS之搜索顺序——AcWing 1116. 马走日
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 25;

int t, n, m;
char g[N][N];
bool st[N][N];
// 注意由于这里我们需要恢复现场，所以递归完后st也会恢复最初状态，不用每次memset重新初始化
int ans;
// 统计方案数的方法多种
// 一种是使用全局变量
// 一种是作为返回值，dfs内使用cnt，并在return时返回
// 一种是作为形参记录当前节点信息

// 枚举表示左右所有方向
int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
int dy[] = {-1, -2, -2 ,-1, 1, 2, 2, 1};

void dfs(int x, int y, int cnt){
    // 判断是否满足边界条件
    // 注意这里为了便于判断，引入的辅助变量cnt，用于记录已遍历的节点个数
    // 之所以要记录是因为每个搜索方案都对应于一个从根节点到叶子节点的走法，必须判断何时到达叶子节点
    // 参数是进行前传(作为返回值)，还是后传(作为形参)，还是使用全局变量：
    // 这里cnt在前面就已经确定，与前面的递归有关，且用于当前状态，所以后传
    // 前传一般用于可分解为无后效的子问题时，且必须要递归返回后，当前状态的量才能确定
    // 全局变量用于记录路径总数等
    
    if  (cnt == n * m){
        ans ++;
        return ;
    }
    st[x][y] = true;
    
    // 枚举所有可移动方向
    for (int i = 0; i < 8; ++ i){
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b]) continue;
        
        dfs(a, b, cnt + 1);
        // 注意形参是要变化的
    }
    
     st[x][y] = false;
     // 注意回溯后恢复现场
     // 注意题目没有确定的终点，而是求遍历所有点的路径
     // 因此每个方格中的点并不对应于搜索状态图中的节点，每个状态节点对应于一个从根节点到叶节点的走法/方案
     // 因此不同方案时方格是可以被重复走的，且需要恢复状态。而标记数组的作用在于每个方案内部时方格只能走一次
     // 也因为没有设定终点，所以需要自己判断是否到了叶子节点
}

int main(){
    scanf("%d", &t);
    while(t --){
        int x, y;
        scanf("%d%d%d%d", &n, &m, &x, &y);
        
        memset(st, 0, sizeof st);
        // 可以不写，因为回溯时会恢复现场
        ans = 0;
        dfs(x, y, 1);
        // 遍历的方格数初始时是1
        printf("%d\n", ans);
    }
    return 0;
}

python

注意python过不了本题

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
from sys import setrecursionlimit

def main():
    setrecursionlimit(5000)
    dir_x = [-2, -1, -1, -2, 2, 1, 1, 2]
    dir_y = [-1, -2, 2, 1, -1, -2, 2, 1]
    T = int(input())
    
    # 使用形参后向传播遍历节点数信息，方便判断是否达到叶子节点
    def dfs(x, y, cnt):
        if not cnt:
            return 1
        # 这里使用前向传参（传返回值）来记录路径总数结果
        way = 0
        vis[x][y] = True
        for dx, dy in zip(dir_x, dir_y):
            nx, ny = x + dx, y + dy
            # 注意这里python关系不等式写法
            if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny]:
                way += dfs(nx, ny, cnt - 1)
        vis[x][y] = False
        return way
        
    for _ in range(T):
        n, m, sx, sy = map(int, input().split())
        vis = [[False] * m for _ in range(n)]
        print(dfs(sx, sy, n * m - 1))

if __name__ == '__main__':
    main()

2. AcWing 1117. 单词接龙

搜索顺序：把开头字母作为根节点，首先枚举以其开头的单词，然后针对每个单词枚举可以接在其后面的单词，直到找不到为止。

由此，第一层和后续层的搜索操作是不同的，为了方便，我们先直接枚举第一层，并当作森林分别进行DFS

这里难点在于：

  • 如何判断两个单词能否接在一起，并记录其重合长度

显然也需要进行枚举。这里为了方便截取子串，可以使用string的substr函数。

注意这里的贪心思想！为了使长度最长，重合的要最小即可。

为了记录每两个单词的最小重合长度，可以建立一个二维数组事先记录。而判断能否相接的过程要在DFS前预处理好

C++

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// DFS之搜索顺序——AcWing 1117. 单词接龙 
// 多入口DFS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 25;

int n;
string word[N]; // 存储所有单词
int g[N][N]; // 图不是直接存在的，而需要构建和存储
//为了使长度最长，重合的要最小即可。因此邻接矩阵g[N][N]除了存储两个单词是否有边，还要具体表示前一单词前缀和后一单词后缀的最小重合长度
int used[N]; // 记录每个单词使用次数
int ans; // 全局变量记录结果

// 传入接龙字符串和拼接的最后一个单词的索引
// 传入拼接的最后一个单词的索引是为了方便进行下一个单词的遍历搜寻
void dfs(string dragon, int last){
    ans = max((int)dragon.size(), ans);
    // 注意size()要强制转换为int，否则类型不对
    // 更新字符串长度

    used[last] ++; // 标记：使用次数加1
	
    // 枚举所有单词
    for (int i = 0; i < n; ++ i)
        if (g[last][i] && used[i] < 2)
            dfs(dragon + word[i].substr(g[last][i]), i);
            // 对于重复的问题，不用进行预先分割当复杂的操作
            // 记录长度后直接用substr对应截取即可
    used[last] --;
    // 回溯时恢复现场
    // 同样不要放在for循环内，循环内仍是在对下一层进行枚举，不需要恢复当前状态
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) cin >> word[i];
    char start;
    cin >> start;
    // scanf("\n%c", &start);

    // 枚举所有单词，判断两两之间是否相接，并记录最小重合长度
    // 这里注意由于每个单词可以使用两次，所以可以自己和自己相接
    // 如果限制了不能自己和自己相接，遍历时要把自己挖出
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < n; ++ j){
            string a = word[i], b = word[j];
            // 分别从前一个单词的结尾和后一个单词的开头进行枚举
            // 注意使用string的substr函数直接截取字串，简化操作
            for (int k = 1; k < min(a.size(), b.size()); ++ k) 
            // 注意题意限制：重合长度必须大于等于1，且严格小于两个串的长度
                // k < min(a.size(), b.size())即可限制严格小于两个串的长度
                if (a.substr(a.size() - k, k) == b.substr(0, k)){
                    g[i][j] = k;
                    break;
                }
        }

    for (int i = 0; i < n; ++ i)
        if (word[i][0] == start)
            dfs(word[i], i); // 传入单词和其索引

    // 搜索顺序：把开头字母作为根节点，首先枚举以其开头的单词，然后针对每个单词枚举可以接在其后面的单词，直到找不到为止。
    // 由于第一层和后续层的搜索操作是不同的，为了方便，我们先直接枚举第一层，并当作森林分别进行dfs
    
    
    printf("%d\n", ans);
    return 0;
}

python

多入口DFS
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
# DFS之搜索顺序——AcWing 1117. 单词接龙 
# 多入口DFS
from sys import setrecursionlimit

def main():
    setrecursionlimit(5000)
    n = int(input())
    g = [[0] * n for _ in range(n)]
    word = [input() for _ in range(n)]
    start = input()
    used = [0] * n
    ans = 0  
    
    def dfs(l, last):
        nonlocal ans 
        # nonlocal声明的变量不是局部变量,也不是全局变量,而是外部嵌套函数内的变量
        ans = max(ans, l)
        
        used[last] += 1
        for i in range(n):
            if g[last][i] and (used[i] < 2):
                dfs(l + len(word[i]) - g[last][i], i)
        used[last] -= 1
    
    for i in range(n):
        for j in range(n):
            w1, w2 = word[i], word[j]
            for k in range(1, min(len(w1), len(w2))):
                # if word[i][len(w1) - k:] == word[j][0:k]:
                if word[i].endswith(word[j][:k]):
                    g[i][j] = k
                    break
    
    # 多入口，根节点确定，但需要遍历其所有子节点
    for i in range(n):
        if word[i][0] == start:
            dfs(len(word[i]), i)
    
    print(ans)
        
if __name__ == "__main__":
    main()
单入口DFS
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
from sys import setrecursionlimit

def main():
    setrecursionlimit(10000)
    n = int(input())
    used = [0] * (n + 1)
    word = [input() for _ in range(n)]
    # 加个哨兵为让 head 直接搜
    # 构造出了符合子节点条件的根节点，使其能当作普通节点处理
    head = '#' + input()
    ans = 0
    
    # dragon 为当前接龙得到的字符串，idx 是上一层 DFS 用到了哪个编号的字符串
    def dfs(dragon, last):
        nonlocal ans
        ans = max(ans, len(dragon))
        
        used[last] += 1
        
        for i, p in enumerate(word):
            # 取 dragon 和 p 中的长度最小值做上界
            for j in range(1, min(len(dragon), len(p))):
                # p 的前缀必须是 dragon 的后缀，且之前的使用次数少于两次
                # 直接使用endswith判断字符串是否以指定字符或子字符串结尾。
                if used[i] < 2 and dragon.endswith(p[:j]):
                    dfs(dragon + p[j:], i)
        used[last] -= 1 
    
    # head 的 idx 取 n，不影响其他元素
    dfs(head, n)
    
    # 减去 '#' 贡献的长度
    print(ans - 1)
    
if __name__ == '__main__':
    main()

3. AcWing 1118. 分成互质组

DFS的一大难点是建图的过程，把问题转化为图论搜索问题。本题的问题是给定n个正整数，将它们分组，使得每组中任意两个数互质。

最初做题时你可能想不到要建图进行搜索，这说明你建图的思想还不足。我们可以如下建图：如果两个数不互质，两者间就有边。要将相互间没有边的分到一组。

互质的判断——最大公约数为1。

这有些类似于求最大团的问题。最大团问题（Maximum Clique Problem, MCP）是图论中一个经典的组合优化问题，也是一类NP完全问题。最大团问题又称为最大独立集问题（Maximum Independent Set Problem）。

暴搜题很多是NP完全问题，否则会考贪心或dp

核心问题是搜索顺序问题，如何把所有情况全部枚举到，求到最优方案。本质是最优化问题。

采用暴搜——决策树模型的策略，进行DFS。由于数和组都是变的，需要以其中一个为主顺序进行枚举决策。

一个组一个组的枚举，看每个组应该选谁。而对于每个组，分别枚举其每个可能放入的数。注意由于所有数都是事先知道的，所以每个组处理完后后面就不会再进行增加和改变。

每种方案都对应一个分支，每次决策后向下递归一层，直到将所有数分完后结束，并更新最小值

注意搜寻顺序：这里可以由两种搜寻顺序：

  1. 对每个数搜寻能在哪个组中

  2. 对每个现有组搜寻所有能放入的数，一个组一个组的枚举

这里如果对每个数进行搜索会比较麻烦，数是变的，组数也是变的，最好能确定一个相对变化不大的（一个数只对应一个组，一个组则对应多个数，枚举组的话总层数少）。这里枚举组，每次把所有能放入的数都放入当前组，然后就不再往当前组的状态进行改变了，而是新开其他组，直至所有数都入组。即每次只对最后一个组进行放入操作。这恰是一种贪心策略，最后能保证组数最少。

所有决策方式：

  1. 把某个数加到最后一组中（规定顺序是一个组一个组枚举，加入组时不是任意的，而是要加到最后一组，使决策更少）

  2. 新开一个组

考虑搜索顺序/决策方式的一个原则是保证让搜索空间尽量小一些，即分支数量少一些。

第一个剪枝优化：

当可以进行第一个操作时就不用进行第二个操作，新开一个组，可以用扰动证明。这可视为了贪心的策略或剪枝优化的策略。

第二个剪枝优化：

进行第一个操作时也可以进行优化。将数放入组中是一个组合问题，不用考虑顺序。这样能够避免组内冗余（排列变组合）

如何实现组合类型递归搜索呢——为了保证不重复搜索，人为规定一个特定搜索顺序即可，如按下标从小到大——需要传入一个形参，记录当前的搜索位置。

第三个剪枝优化

同时由于本题求的是最小值，可以使用最优性剪枝优化，但结果已经大于当前最优解则剪枝。

dfs分组问题有两种做法，第一种就是：枚举每个数要分到哪一组，这种的话没有等效冗余，第二种：枚举哪一组应该放进那些数，这种需要优化等效冗余，

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// DFS之搜索顺序——AcWing 1118. 分成互质组
// 静态数组的思路，为每个组找数字
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 25;

int n;
int p[N];
int group[N][N]; // 每组分别记录下来，最坏情况下每个节点一组
bool st[N];
int ans = N; // 最坏情况下每个节点一组
// 注意由于ans要取最小值，所以初始时要赋无穷大或大于理论上的最大值

// 欧几里得算法求最大公约数
// 最大公约数等于1说明互质
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

// 判断一个数是否能放入当前的组中
bool check(int group[], int gc, int i){
    // 枚举所有已放入组中的数，判断是否互质
    for (int j = 0; j < gc; ++ j)
        if (gcd(p[group[j]], p[i]) > 1)
            return false;
    return true;
}

// 注意形参的设置
// g记录当前的总组数，也恰好是当前最后一个组的编号
// gc记录当前最后一个组已放入的数的个数
// tc表示当前已分配好的数的个数，用于判断是否结束
// start表示还未分配的数中第一个数的下标
// 这里需要注意要按照组合类型的搜索方式，即认为规定一个特定搜索顺序，这里按照下标顺序
void dfs(int g, int gc, int tc, int start){
    if (g >= ans) return;
    // 最优性剪枝，当结果大于等于目前的最优解时，一定不是最优解，直接返回
    if (tc == n){
        ans = g;
        return;
    } 
    // 由于前面的判断，所以现在一定小于目前的解，进行更新

    // 设置一个标记，用于判断是否需要新开一个组
    bool flag = true;
    // 新开一个组的条件：枚举剩余所有数后都不存在新的点可以放入当前组

    // 从未分配的数中第一个数开始枚举，分别尝试放入剩余的数，进行递归搜索
    for (int i = start; i < n; ++ i)
        if (!st[i] && check(group[g], gc, i)){
            st[i] = true; // 标记已分配好
            group[g][gc] = i; // 存入数的索引编号
            // 进行递归
            dfs(g, gc + 1, tc + 1, i + 1);
            // 注意形参的对应变化

            st[i] = false;
            // 回溯时恢复现场，注意这里改变的是被枚举的数的状态，所以在循环内部恢复
            // group[g][gc]由于会直接被覆盖，不用恢复
            flag = false;
            
            // 剪枝——组合问题规定特定顺序
            if (gc == 0)
                break;
            // 因为开一个新组的前提条件是每个数都不能放到旧组中了，
            // 所以剩下的第一个数一定会放到某个新组中，而组与组之间是没有顺序的区别的
            // 比如对于数据3，7，6，14来说，第一次搜索结束后{3, 14}, {7，6}被找到，
            // 后续是不需要找{7, 6}, {14, 3}的，所以可以直接规定一种顺序——未分配的数直接放入新的组中
            // 那我们可以将它固定到第一个新组中，这样可以减掉很多等效冗余的方案。
        }  

    // 如果枚举了所有剩余的数都不能放入当前组，就新开一个组
    if (flag) dfs(g + 1, 0, tc, 0);
    // 新开一个组，注意此时需要将gc和start设为0, g加1，而tc不变
}

int main(){
    scanf("%d", &n);

    for (int i = 0; i < n; ++ i) scanf("%d", &p[i]);

    dfs(1, 0, 0, 0);
    // 注意初始形参的大小

    printf("%d\n", ans);
    return 0;
}

python

静态数组的思路，为每个组找数字。

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
# DFS之搜索顺序——AcWing 1118. 分成互质组
# 静态数组的思路，为每个组找数字
from sys import setrecursionlimit

def main():
    n = int(input())
    p = list(map(int, input().split()))
    group = [[0] * n for _ in range(n)]
    vis = [False] * n
    ans = n
    
    def gcd(a, b):
        return gcd(b, a % b) if b else a
    
    def check(group, gc, i):
        for j in range(gc):
            if gcd(p[group[j]], p[i]) > 1:
                return False
        return True
    
    def dfs(g, gc, tc, start):
        nonlocal ans 
        if g >= ans:
            return
        if tc == n:
            ans = g
            return 
        
        flag = True
        for i in range(start, n):
            if not vis[i] and check(group[g], gc, i):
                vis[i] = True
                group[g][gc] = i
                flag = False
                dfs(g, gc + 1, tc + 1, i + 1)
            
                vis[i] = False
                if not gc:
                    break
        if flag:
            dfs(g + 1, 0, tc, 0)
    
    dfs(1, 0, 0, 0)
    print(ans)
    
if __name__ == "__main__":
    main()

动态数组思路，为每个数字找组

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
# DFS之搜索顺序——AcWing 1118. 分成互质组
# 动态数组思路，为每个数字找组
from math import gcd
# 返回最大公约数

def main():
    n = int(input())
    p = list(map(int, input().split()))
    # 求出所有互质的一对数
    coprime = {(x, y) for x in p for y in p if gcd(x, y) == 1}
    group = [[] for _ in range(n)]
    res = n
    
    # 回溯法，为每个 p[idx] 找到合适的组
    # idx为当前要分配的数的索引
    # group 为预设的空组，size 为存在元素的组个数
    def backtrace(idx, size):
        nonlocal res
        # 剪枝 and 刷新答案
        if size >= res or idx == n:
            res = min(res, size)
            return
        cur = p[idx]
        # 尝试将 p[idx] 插入当前存在元素的组（group 中前 size 个组）
        for g in group[:size]:
             # 查询当前 p[idx] 与组 g 中元素组成的二元组是否都在 coprime 中
             if all((cur, val) in coprime for val in g):
                 g.append(cur)
                 backtrace(idx + 1, size)
                 g.pop() # 回溯恢复现场
        # 新开一组，插入 p[idx]
        group[size] = [cur]
        backtrace(idx + 1, size + 1)
        group[size] = [] # 回溯恢复现场
    
    backtrace(0, 0)
    print(res)
    
if __name__ == "__main__":
    main()

状压 DP

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
# DFS之搜索顺序——AcWing 1118. 分成互质组
# 状压 DP
from math import gcd

def main():
    n = int(input())
    p = list(map(int, input().split()))
    # 求出所有互质的一对数
    coprime = {(x, y) for x in p for y in p if gcd(x, y) == 1}
    dp = [n] * (1 << n) # 2^n
    # 使用二进制状态表示出所有可能的分组的情况
    
    # 检查当前状态的所有元素是否满足组内互质
    # all 中 iterator 为空时也返回 True，满足单个元素的答案情况
    def helper(mask):
        # 使用二进制保存当前组中包含的数，1为包含，0为不包含
        # x >> i & 1用来判断第i位是0还是1
        g = [p[idx] for idx in range(n) if mask >> idx & 1]
        return all((g[i], g[j]) in coprime for i in range(len(g)) 
        for j in range(i + 1, len(g)))
    
    # 从小到大转移，枚举子集的状压 DP
    for i in range(1, 1 << n):
        # 满足组内互质的二进制对应分组
        if helper(i):
            dp[i] = 1
            continue
    
        # 枚举一半子集即可，剪枝
        j, split = (i - 1) & i, i >> 1
        # 状压 DP
        while j > split:
            dp[i] = min(dp[i], dp[j] + dp[i^j])
            j = (j - 1) & i
    print(dp[-1])
    
if __name__ == "__main__":
    main()