并查集7.9.21.并查集的定义给定n个结点的集合，结点编号为1～n，再给定一个等价关系，由等价关系产生所有结点的一个划分，每个结点属于一个等价类，所有等价类是不相交的。需要求一个结点所属的等价类，以及合并两个等价类。求解该问题的基本运算(1)Init()：初始化。加(2)Find（intx）：查找x结点所属的等价类。(3)Union(int x，inty)：将x和y所属的两个等价类合并。上述数据结构称为并查集
1. 并查集的定义 给定n个结点的集合，结点编号为1～n，再给定一个等价关系， 由等价关系产生所有结点的一个划分，每个结点属于一个等价类， 所有等价类是不相交的。 需要求一个结点所属的等价类，以及合并两个等价类。 （1）Init()：初始化。 （2）Find(int x)：查找x结点所属的等价类。 （3）Union(int x，int y)：将x和y所属的两个等价类合并。 求解该问题的基本运算 上述数据结构称为并查集
2.并查集的实现并查集就是一个森林。每个等价类用一棵树表示，包含该等价类的所有结点，即结点子集。每个子集通过一个代表来识别，代表即该子集中的某个结点，通常选择根做这个代表
2. 并查集的实现 并查集就是一个森林。 每个等价类用一棵树表示，包含该等价类的所有结点，即结点子集。 每个子集通过一个代表来识别，代表即该子集中的某个结点，通常 选择根做这个代表。 A x y
经典示例问题描述：如果已经得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好代，使得家谱于分庞大，那么检验亲戚关系就十分复杂。在这种情况下，就需要应用并查集。为了将问题简化，将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，可以推出Marry和Ben是亲戚
问题描述：如果已经得到完整的家谱，判断两个人是否亲戚应该是 可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十 分庞大，那么检验亲戚关系就十分复杂。在这种情况下，就需要应用并 查集。 为了将问题简化，将得到一些亲戚关系的信息，如Marry和Tom是 亲戚，Tom和Ben是亲戚，等等。从这些信息中，可以推出Marry和Ben 是亲戚。 经典示例
输入：第一部分以N， M开始。N为问题涉及的人的个数（1≤N≤20000）这些人的编号为1，2，3，，N。下面有M行（1≤M≤1000000），每行有两个数ai、bi，表示已知a,和b,是亲戚。第二部分以Q开始。以下Q行有Q个询问（1≤Q≤1000000），每行为c,和di，表示询问c,和d,是否为亲戚。输出：对于每个询问ci、di，输出一行：若c,和d,为亲戚，则输出"Yes",否则输出"No"。解决分类问题
输入：第一部分以N，M开始。N为问题涉及的人的个数（1≤N≤20000）。 这些人的编号为1，2，3，.， N。 下面有M行（1≤M≤1000000），每行有两个数ai、bi，表示已知ai和bi是亲 戚。 第二部分以Q开始。以下Q行有Q个询问（1≤Q≤1000 000），每行为ci和di， 表示询问ci和di是否为亲戚。 输出：对于每个询问ci、di，输出一行：若ci和di为亲戚，则输出"Yes"， 否则输出"No"。 解决分类 问题
输入样例：1071/N=10,M=7A2类似于离散数学中的等价类问题：7-给定一个集合U和一个等价关系R，产生具X有等价关系的等价类。56中231 /Q=33A37.1089
输入样例： 10 7 //N=10，M=7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 //Q=3 3 4 7 10 8 9 类似于离散数学中的等价类问题： 给定一个集合U和一个等价关系R，产生具 有等价关系的等价类