题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
from sys import stdin
from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10000000)
def dfs(root):
if not g[root]:
f[root][0] = 0
f[root][1] = 1
return
for i in g[root]:
dfs(i)
f[root][1] = 1
for a in g[root]:
f[root][0]+=f[a][1]
f[root][1]+= min(f[a][0],f[a][1])
while True:
try:
n = int(stdin.readline())
g = defaultdict(list)
is_root = [1 for i in range(n+10)]
for i in range(n):
w = list(map(str, input().split()))
a, _ = w[0].split(':')
for wi in w[1 : ]:
g[int(a)].append(int(wi))
is_root[int(wi)]=0
# print(g)
f = [[0]*2 for i in range(n+10)]
for i in range(n):
if is_root[i]:
# print(i)
dfs(i)
roots = i
break
print(min(f[roots][0],f[roots][1]))
except:
break
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla