请编写程序,实现采用按秩合并策略的不相交集的基本操作。
所谓“按秩合并策略”是指:集合元素 i 和 j 合并时,如果两个集合的秩(rank)相等,则总是将 i 所在的集合并入 j 所在的集合,即合并后集合的名称为 j 所在的集合名称,同时将合并后的集合秩增 1;否则总是将秩小的集合并入秩大的集合。
输入格式:
输入首先在第一行给出两个正整数,依次为集合中元素个数 n(1<n≤100)和元素之间的关系数 m(≤n)。
随后 m 行,每行给出一对等价元素的编号,从 1 开始。同行数字均以一个空格分隔。
接下来给出一个正整数 k(≤100),随后 k 行,每行给出一对待查询的关系,即一对元素的编号。
输出格式:
参考样例。
首先输出集合中每个元素的信息,格式为
set[i].parent = j, rank = k
表示编号为 i
的元素的父结点编号为 j
,该结点存储的秩的值为 k
(每个结点的初始秩默认为 0)。按 i
的升序输出。如果 i
没有父结点,则规定 set[i].parent = i
。
随后对每一对待查询的关系,如果它们属于同一个等价集合,就在一行中输出 yes
,否则输出 no
。
输入样例:
8 5
1 4
2 3
3 5
4 2
6 7
7
1 3
4 5
5 1
2 5
6 8
4 8
3 7
输出样例:
set[1].parent = 4, rank = 0
set[2].parent = 3, rank = 0
set[3].parent = 3, rank = 2
set[4].parent = 3, rank = 1
set[5].parent = 3, rank = 0
set[6].parent = 7, rank = 0
set[7].parent = 7, rank = 1
set[8].parent = 8, rank = 0
yes
yes
yes
yes
no
no
no