若将森林中的每棵树视作一个等价类,则Kruskal算法迭代过程所涉及的计算不外乎两类:
支持以上操作接口的数据结构,即所谓的独立集(disjoint set),亦称作并查集(union-find set)。
a)试基于此前介绍过的基本数据结构实现并查集,并用以组织Kruskal算法中的森林;
b)按你的实现,find()和union()接口的复杂度各是多少?相应地,Kruskal算法的复杂度呢?
在顺序存储结构上实现输出受限的双端循环队列的入列和出列(只允许队头出列)算法。设每个元素表示一个待处理的作业,元素值表示作业的预计时间。入队列采取简化的短作业优先原则,若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间,则插入在队头,否则插入在队尾。
问题描述:给定两个n×n矩阵A和B,试设计一个判定A和B是否互逆的蒙特卡罗算法(算法的计算时间应为O(n2).
算法设计:设计一个蒙特卡罗算法,对于给定的矩阵A和B,判定其是否互逆.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示矩阵A和B为n×n矩阵.接下来的2n行,每行有n个实数,分别表示矩阵A和B中的元素.
结果输出:将计算结果输出到文件output.txt.若矩阵A和B互逆,则输出“YES",否则输出“NO".