试基于BFS搜索设计并实现一个算法，在o（n+e)时间内将任一无向图分解为一组极大连通域。

若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：

支持以上操作接口的数据结构，即所谓的独立集(disjoint set)，亦称作并查集(union-find set)。

a)试基于此前介绍过的基本数据结构实现并查集，并用以组织Kruskal算法中的森林;

b)按你的实现，find()和union()接口的复杂度各是多少？相应地，Kruskal算法的复杂度呢？

如果在合并排序算法的分割步骤中,将数组a[0:n-1]划分为[ ]个子数组,每个子数组中有O()个元素,然后递归地对分割后的子数组进行排序,最后将所得到的[ ]个排好序的子数组合并成所要求的排好序的数组a[0;n-1].设计一个实现上述策略的合并排序算法,并分析算法的计算复杂性.

Ackermann函数A(m,n)可递归定义如下:

试设计一个计算A(m,n)的动态规划算法,该算法只占用O(m)空间(提示:用两个数组val[0:m]和ind[0:m],使得对任何i有val[i]=A(i,ind[i])).

问题描述:给定两个n×n矩阵A和B,试设计一个判定A和B是否互逆的蒙特卡罗算法(算法的计算时间应为O(n²).

算法设计:设计一个蒙特卡罗算法,对于给定的矩阵A和B,判定其是否互逆.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示矩阵A和B为n×n矩阵.接下来的2n行,每行有n个实数,分别表示矩阵A和B中的元素.

结果输出:将计算结果输出到文件output.txt.若矩阵A和B互逆,则输出“YES",否则输出“NO".

习题[4-18](108页)曾指出，同一整数可能同时存在多个费马-拉格朗日(Fermat-Lagrange)分解，其中，四个整数之和最小者称作最小分解，比如：

其中(0，0，1，10)即为101的最小费马-拉格朗日分解，因为组成它的四个整数之和11为最小。

a)试设计并实现一个算法，对任何整数n＞0，输出[1，n]内所有整数的最小费马-拉格朗日分解;

b)你的算法需要运行多少时间？空间呢？