并查集基础与应用：亲戚关系查询

"该资源是关于并查集(Disjoint Sets)的基础介绍，主要讨论了如何使用并查集解决不相交集合的合并与查询问题。文中通过一个亲戚关系的例子来阐述并查集的应用，包括数据输入和输出的格式描述。" 在程序设计中，并查集是一种高效处理不相交集合合并与查询的数据结构。它主要用于解决一类问题，即在一个动态变化的集合系统中，判断两个元素是否属于同一个集合，以及合并两个集合。并查集的核心操作包括： 1. **初始化**：通常采用数组`father`来表示每个元素的父节点，初始化时，每个元素都以自己为根节点，即`father[i] = i`。 2. **查找操作**（Find）：用于确定一个元素所在的集合，通常采用路径压缩技术提高效率，即在查找过程中将沿途的节点都指向最近的根节点，以减少后续查询的时间。 3. **合并操作**（Union）：将两个集合合并为一个，一般选取根节点值较小的集合合并到根节点值较大的集合，或者选择根节点深度较浅的集合合并到深度较深的集合，以保持树的平衡，减少查询时的路径长度。 4. **路径压缩**：在查找过程中，每次找到一个节点的父节点，都将这个节点直接指向其祖父节点，从而减少后续查找的层次，提高查找效率。 在给定的例子中，假设有一个亲戚关系的问题，有n个人，m个亲戚关系，以及p个询问。数据输入包括三部分：n、m、p的值，接着是m对亲戚关系的表示，最后是p对询问关系。程序需要根据这些数据，利用并查集来判断任意两个人之间是否存在亲戚关系。输出是对每个询问的响应，如果是亲戚则输出"Yes"，否则输出"No"。 在实际应用中，除了亲戚关系查询，并查集还常用于网络连接状态判断、图形连通性分析、活动安排等多个场景，其高效的操作特性使其在算法设计中占据重要地位。并查集的设计和优化，如路径压缩和加权快速联合等策略，都是算法竞赛和实际编程中需要掌握的关键技巧。