回溯 DFS——连通性和搜索顺序( 三 ) _dfs

这里cnt对应于终止条件，路径选择只需要保证合法性和树枝去重即可
单词接龙
单词接龙是一个与我们经常玩的成语接龙相类似的游戏。
现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。
在两个单词相连时，其重合部分合为一部分，例如 beast 和，如果接成一条龙则变为。
我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。
你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
数据范围
n≤20，
单词随机生成。
输入样例：
at
touch
cheat
tact
输出样例：
23
提示
连成的“龙”为 ose 。
N = 25p = []g = [[0] * N for _ in range(N)]used = [0] * Nans = 0def dfs(dragon, last) : #last参数是为了判断路径选择的合法性和树枝去重global ansans = max(ans, len(dragon))used[last] += 1for i in range(n) :if used[i] < 2 and g[last][i] :dfs(dragon + p[i][g[last][i] :], i)used[last] -= 1n = int(input())for i in range(n) :p.append(input())st = input()for i in range(n) :for j in range(n) :a, b = p[i], p[j]for k in range(1, min(len(a), len(b))) :if a[-k :] == b[:k] :g[i][j] = kbreakfor i in range(n) :if p[i][0] == st :dfs(p[i], i)print(ans)
分成互质组
给定 n 个正整数，将它们分组，使得每组中任意两个数互质。
至少要分成多少个组？
输入格式
第一行是一个正整数 n 。
第二行是 n 个不大于10000的正整数。
输出格式
一个正整数，即最少需要的组数。
数据范围
1≤n≤10
输入样例：
14 20 33 117 143 175
输出样例：
N = 15st = [False] * Ngroup = [[0] * N for _ in range(N)]ans = Ndef gcd(a, b) : #return a if b == 0 else gcd(b, a % b)def check(group, gc, i) : #判断i与group数组中所有元素是否互质for j in range(gc) :if gcd(p[group[j]], p[i]) > 1 :return Falsereturn Truedef dfs(g, gc, ct, start) :global ansif g >= ans : return # 优化剪枝if ct == n : ans = g # 终点终止条件flag = True #判断是否可能被划分到g组for i in range(start, n) :if not st[i] and check(group[g], gc, i) :st[i] = Truegroup[g][gc] = idfs(g, gc + 1, ct + 1, i + 1)group[g][gc] = 0st[i] = Falseflag = Falseif flag : dfs(g + 1, 0, ct, 0) #开一个新组n = int(input())p = list(map(int, input().split()))dfs(1, 0, 0, 0)print(ans)
总结
dfs分为连通（内部）dfs和回溯（外部）dfs，回溯dfs的枚举又分为枚举排列和组合类型的问题。