Python获取能唯一确定一棵给定的树的最少数量的拓扑序列

称一个$1$~$n$的排列 { p } = { p 1 , p 2 , ⋯ , p n } \{p\}=\{p_1,p_2,\cdots,p_n\} {p}={p1​,p2​,⋯,pn​}是一棵n个点、点编号为$1$至$n$的树$T$的拓扑序列，当且仅对于任意$1\le i<n$，恰好存在唯一的$j>i$满足$p_i$与$p_j$之间有连边。
给定树$T$，你需要给出尽可能少的该树的拓扑序列 { p 1 } , { p 2 } , ⋯ , { p k } \{p_1\},\{p_2\},\cdots,\{p_k\} {p1​},{p2​},⋯,{pk​}，使得有且仅有树T满足 { p 1 } , { p 2 } , ⋯ , { p k } \{p_1\},\{p_2\},\cdots,\{p_k\} {p1​},{p2​},⋯,{pk​}均为该树的合法拓扑序列。
【输入格式】
从标准输入读入数据。
本题有多组测试数据。输入第一行一个正整数$T$，表示测试数据组数，接下来依次输入每组测试数据。
对于每组数据，输入第一行一个正整数$n$，表示给定树的大小。接下来$n-1$行，每行两个正整数$u$,$v$描述树中存在的一条边。

【输出格式】
输出到标准输出。
对于每组数据，输出第一行一个正整数k表示你给出的拓扑序列数量，接下来k行，每行输出一个$1n$的排列，描述你给出的拓扑序列。你需要保证$1\le k\le n$，且这$k$个拓扑序列均为对应输入的合法拓扑序列，且只有一棵树满足这些拓扑序列都是其合法拓扑序列。
【样例1输入】

1
2
5
2 3
3 1
5 1
5 4
5
1 4
2 3
3 1
5 3

【样例输出】

2
2 3 1 5 4
4 5 1 3 2
2
4 1 5 3 2
2 5 3 4 1

【子任务】

• 描述了对于所有测试数据的要求：1 ≤ T ≤ 100，3 ≤ n ≤ 100，1 ≤ u, v ≤ n。
• 本题共有两个测试点。
• 测试点编号、分值、T 和 n 的具体信息如下：
  • 测试点1：分值20，T = 10，n = 10。
  • 测试点2：分值80，T = 10^2，n = 10^2。
• 特别说明：所有测试点中每组数据均为从所有 n 个点的有标号树中等概率随机选择生成的。
  为了解决这个问题，我们需要构造尽可能少的拓扑序列，使得这些序列能够唯一确定给定的树结构。通过分析问题，我们可以利用树的直径的两个端点来生成两个拓扑序列，这两个序列的组合可以唯一确定树的结构。

以下方法通过利用树的直径的两个端点生成两个不同的拓扑序列，确保这两个序列的组合能够唯一确定原树的结构，从而满足题目要求。

方法思路

1. 确定树的直径：树的直径是树中最长的路径。通过两次广度优先搜索（BFS）可以找到直径的两个端点。
2. 生成拓扑序列：分别以直径的两个端点作为根节点，生成两个拓扑序列。每次选择离根节点最远的叶子节点，直到只剩下根节点。

解决代码

import sys
from collections import deque
import copydef main():input = sys.stdin.read().split()ptr = 0T = int(input[ptr])ptr +=1for _ in range(T):n = int(input[ptr])ptr +=1adj = [[] for _ in range(n+1)]for __ in range(n-1):u = int(input[ptr])v = int(input[ptr+1])ptr +=2adj[u].append(v)adj[v].append(u)# Find diameter endpointsdef bfs(start):visited = [False]*(n+1)q = deque([start])visited[start] = Truelast_node = startdistance = 0dist = [0]*(n+1)while q:for _ in range(len(q)):u = q.popleft()for v in adj[u]:if not visited[v]:visited[v] = Truedist[v] = dist[u] +1q.append(v)last_node = vif q:distance +=1return (last_node, dist)u, _ = bfs(1)v_end, dist_v = bfs(u)v = v_endu_end, dist_u = bfs(v)u = u_enddef generate_sequence(root):seq = []removed = [False]*(n+1)parent = [0]*(n+1)current_adj = copy.deepcopy(adj)for _ in range(n-1):# Compute distances from root using BFS on remaining nodesdist = [-1]*(n+1)q = deque()q.append(root)dist[root] =0while q:u_node = q.popleft()for v_node in current_adj[u_node]:if not removed[v_node] and dist[v_node] == -1:dist[v_node] = dist[u_node] +1parent[v_node] = u_nodeq.append(v_node)# Find leaves (degree 1 in current tree) not rootleaves = []for node in range(1, n+1):if removed[node] or node == root:continuecnt =0for neighbor in current_adj[node]:if not removed[neighbor]:cnt +=1if cnt ==1:leaves.append(node)if not leaves:break# Select the leaf with maximum distance to rootmax_dist = -1selected = Nonefor leaf in leaves:if dist[leaf] > max_dist:max_dist = dist[leaf]selected = leafseq.append(selected)removed[selected] = True# Update parent's degree is handled implicitly by 'removed'seq.append(root)return seqs1 = generate_sequence(u)s2 = generate_sequence(v)# Outputprint(2)print(' '.join(map(str, s1)))print(' '.join(map(str, s2)))if __name__ == '__main__':main()

代码解释

1. 输入处理：读取输入数据并构建树的邻接表。
2. 确定直径端点：通过两次BFS找到树的直径的两个端点。
3. 生成拓扑序列：以每个直径端点为根，生成拓扑序列。每次选择离根节点最远的叶子节点，直到只剩下根节点。
4. 输出结果：输出两个拓扑序列，确保它们唯一确定原树的结构。