ramsol @ 2023-04-13 14:51:18
import collections
n = int(input())
nxs = collections.defaultdict(list)
dp = [[0]*2 for _ in range(n)]
flag = [1] * n
for _ in range(n):
nums = list(map(int, input().split()))
p, s = nums[0], nums[1]
for i in range(s):
nxs[p].append(nums[i+2])
flag[nums[i+2]] = 0
def dfs(i):
global dp
if i in nxs:
for j in nxs[i]:
dfs(j)
dp[i][0] += dp[j][1]
dp[i][1] += min(dp[j][0], dp[j][1])
dp[i][1] += 1
for i in range(n):
if flag[i] == 1:
dfs(i)
print(min(dp[i][1], dp[i][0]))
break
go没这个问题
func timu4() {
var n int
fmt.Scan(&n)
nxs := make(map[int][]int, n)
dp := make([][2]int, n)
flag := make([]int, n)
for i := 0; i < n; i++ {
flag[i] = 1
}
for i := 0; i < n; i++ {
var point int
var length int
fmt.Scan(&point, &length)
var a int
tmp := make([]int, length)
for j := 0; j < length; j++ {
fmt.Scan(&a)
tmp[j] = a
flag[a] = 0
}
nxs[point] = tmp
}
var dfs func(int)
dfs = func(i int) {
for _, j := range nxs[i] {
dfs(j)
dp[i][1] += min(dp[j][0], dp[j][1])
dp[i][0] += dp[j][1]
}
dp[i][1] += 1
}
for i := 0; i < n; i++ {
if flag[i] == 1 {
dfs(i)
fmt.Println(min(dp[i][0], dp[i][1]))
break
}
}
}
by Terrible @ 2023-04-13 15:51:33
@ramsol
提示:你通过本题后可以看别人的代码,找到跟你同样 RE 1点 80分而后修改100分的记录,很容易定位到错误。
通过翻找记录,发现可能是递归超限了,Python 的默认递归上限是 1000 层,使用sys.setrecursionlimit(10000000)
,即可解决问题。
by ramsol @ 2023-04-13 16:05:53
@Terrible 好的好的,谢谢大佬