树的存储和遍历
作者:
成理第一深情
,
2024-01-26 20:33:23
,
所有人可见
,
阅读 52
"""
参考Actor代码
1.图的存储模板:
graph = {} # 字典的形式存图,相当于链表存图,每个键值代表树中的一个节点,其值是列表类型,列表中存的是当前节点所有可以达到的节点
n = int(input().strip())
for i in range(n):
a, b = map(int, input().split()) # a,b分别代表树中的两个节点,现在需要给它们连一条边
if a not in grath:
grath[a] = b
else:
grath[a].append(b)
### 存储无向图
if b not in grath:
grath[b] = [a]
else:
grath[b].append(a)
# 初始化状态数组,不需要像c++一样预先开一个足够大的数组,只需要初始化自己需要的大小
st = [False for _ in range(n+1)]
2.图的深度优先搜索模板
def dfs(u):
# u表示当前搜到的节点
st[u] = True
# 搜u的所有子树
for i in range(grath[u]):
if not st[i]:
dfs(i)
"""
def dfs(u):
global res
st[u] = True
size = 0 # 用来存储以u为根的所有子树的节点的最大值(不包含u节点)
sumNode = 0 # 存储以u为根节点的所有子节点数(不包含u本身),这个变量的作用是为了获取剩下那个连通块中节点的数量,剩下那个连通块中节点数量等于总的节点数量减去以u为根节点的所有子节点数量,再减去u
# 遍历u的子树
for i in graph[u]:
if not st[i]:
s = dfs(i) # 返回u节点的以i为根节点的子树的节点数
sumNode += s
size = max(size, s)
size = max(size, n - sumNode - 1)
res = min(res, size)
return sumNode + 1 # +1:表示包含i节点的总节点数
graph = {}
n = int(input().strip())
# n-1条无向变
for i in range(n - 1):
a, b = map(int, input().strip().split())
if a not in graph:
graph[a] = [b] # 这里一定要是列表的形式
else:
graph[a].append(b)
### 无向边
if b not in graph:
graph[b] = [a] # 这里一定要是列表的形式
else:
graph[b].append(a)
# 初始化状态数组
st = [False for _ in range(n+1)]
res = n
dfs(1)
print(res)