Параллельный алгоритм Краскала С++

Необходимо реализовать программу на VS C++ с использованием MPICH2 (библиотека mpi.h), которая выполняла алгоритм Краскала.
Требования:
1) Матрица смежности как способ представления матрицы (эл-ты матрицы - веса рёбер, главная диагональ 0)
2) Структура хранения матрицы одномерный массив
3) Веса задаются произвольно (от 1), размер матрицы 3000x3000
4) На выходе- матрица смежности, записанная в файл, для остовного дерева, проверка на то, что это дерево
5) Работоспособность на любом числе процессов
6) Понятный код, с грамотными комментариями

матрица смежности может заполниться так, что граф будет не связным ( а такого быть не должно), поэтому нужно это предусмотреть.


программа должна замерять время и должно получиться ускорение