大不相交集基本操作pta

### 大不相交集数据结构基本操作 大不相交集（Disjoint Set Union, DSU），也被称为并查集，是一种用于处理集合合并与查询的数据结构。其核心功能在于高效地支持两种操作：查找某个元素所属的集合以及将两个不同的集合合并成一个新的集合。 #### 查找操作 查找操作的目标是找到给定元素所在的集合代表元。为了提高效率，通常会采用路径压缩技术来优化树的高度。以下是基于路径压缩的查找函数实现： ```python def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) # 路径压缩 return parent[x] ``` 此代码片段展示了如何通过递归的方式进行路径压缩[^1]。 #### 合并操作 当需要将两个不同集合中的元素合并时，可以利用按秩合并策略减少树的高度，从而提升性能。下面是一个典型的合并方法实现： ```python def union(parent, rank, x, y): rootX = find(parent, x) rootY = find(parent, y) if rootX != rootY: if rank[rootX] > rank[rootY]: parent[rootY] = rootX elif rank[rootX] < rank[rootY]: parent[rootX] = rootY else: parent[rootY] = rootX rank[rootX] += 1 ``` 这里实现了带权重的合并逻辑，其中`rank`数组用来记录每个节点作为根节点时子树的高度估计值。 ### PTA 题目解析及相关实现 对于PTA上的具体题目，“两个有序链表序列的交集”的求解可以通过双指针法完成。该算法适用于已经排序好的列表，在遍历过程中比较两者当前指向项大小关系决定移动哪一侧索引位置直到遇到共同数值或者某一边到达终点为止。下面是简化版本解决方案之一： ```python list_a = list(map(int, input().split())) list_b = list(map(int, input().split())) i, j = 0, 0 result = [] while i < len(list_a) and j < len(list_b): if list_a[i] == -1 or list_b[j] == -1: break if list_a[i] < list_b[j]: i += 1 elif list_a[i] > list_b[j]: j += 1 else: result.append(str(list_a[i])) i += 1 j += 1 print(' '.join(result)) ``` 上述脚本读取两行输入分别对应于两个升序排列整数列，并按照指定规则找出它们之间的公共部分输出到标准流上[^2]。