并查集基础：判断元素所属集合与路径压缩

"本文主要介绍并查集这一数据结构，以及如何利用它来判断元素是否属于同一集合。并查集是一种用于处理不相交集合合并的问题的树型数据结构，其主要操作包括合并两个集合、判断两个元素是否在同一集合以及路径压缩。通过一个亲戚关系的例子，解释了如何运用并查集解决实际问题，如查询两个人是否具有亲戚关系。" 在并查集中，每个元素都有一个父亲节点，用来表示它所属的集合。例如，给定的描述中，father数组表示元素i的父亲节点，如father[1]=1表示元素1的父节点是1，这暗示元素1、2、3都在同一个集合中，而元素4的父节点是5，5的父节点是3，这意味着元素4和5在一个集合中，但与1、2、3不在同一集合。 并查集的主要操作包括： 1. **合并两个不相交集合**：当需要将两个集合合并时，通常选择根节点代表整个集合，并将其中一个集合的根节点指向另一个集合的根节点。这个过程也称为“union”操作。在路径压缩的情况下，会沿着从元素到根节点的路径直接将所有节点的父节点指向另一个集合的根节点，以减少后续查询的时间复杂度。 2. **判断两个元素是否属于同一集合**：通过查询两个元素的根节点是否相同来确定。如果它们的根节点相同，则它们属于同一集合；反之，它们属于不同集合。这个过程称为“find”操作。为了提高效率，通常会采用路径压缩技术，即在查询过程中直接将所有节点指向其根节点，这样下次查询时可以直接到达根节点。 3. **路径压缩**：在每次查找根节点的过程中，将沿途经过的所有节点直接链接到根节点，减少树的高度，从而加快查询速度。路径压缩可以显著提高并查集的性能，尤其是在频繁进行find操作时。 在给出的亲戚关系问题中，可以使用并查集来存储每个人及其亲戚关系。当新的亲戚关系建立时，进行合并操作；当询问两个人是否是亲戚时，通过find操作判断他们是否拥有相同的根节点。如果两个人的根节点相同，那么他们就是亲戚，输出"Yes"；否则，输出"No"。 例如，对于输入数据，第一行包含n、m、p，分别表示人数、亲戚关系数量和询问次数。接下来m行表示亲戚关系，每行两个数Mi和Mj表示Ai和Bi是亲戚。最后p行表示询问，每行两个数Pi和Pj询问他们是否是亲戚。程序将使用并查集处理这些关系，快速回答每个询问。