Day53力扣打卡

打卡记录

重新规划路线（dfs）

链接

class Solution:
    def dfs(self, x: int, parent: int, e: List[List[List[int]]]) -> int:
        res = 0
        for edge in e[x]:
            if edge[0] == parent:
                continue
            res += edge[1] + self.dfs(edge[0], x, e)
        return res

    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        e = [[] for _ in range(n)]
        for edge in connections:
            e[edge[0]].append([edge[1], 1])
            e[edge[1]].append([edge[0], 0])
        return self.dfs(0, -1, e)

回路计数（DP状态压缩）

链接

import os
import sys
import math

n = 21
st = [[False] * n for _ in range(n)]
for i in range(0, n, 2):
    for j in range(i + 1, n):
        if math.gcd(i + 1, j + 1) == 1:
            st[i][j] = st[j][i] = True

f = [[0] * n for _ in range(1 << n)]
f[1][0] = 1

for i in range(1 << n):
    for j in range(n):
        if not (i >> j) & 1:
            continue
        for k in range(n):
            if (i >> k) & 1 and st[k][j]:
                f[i][j] += f[i - (1 << j)][k]

ans = 0
for i in range(n):
    ans += f[-1][i]
print(ans)