Дискретная математика. Лабораторная работа №5. Вариант №4

Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа. При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода.
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е. изменять исходный граф без выхода из программы. Предусмотреть также возможность изменения количества вершин.
Вход программы: число вершин графа и матрица смежности.
Выход: разбиение множества вершин на подмножества, соответствующие компонентам связности.
Решение.
Входными данными является число вершин графа num_elements и матрица смежности M типа TMatrix, состоящая из двумерного массива m и размера n. Связанные вершины задаются в виде пар, организованных в виде структур TPair, содержащих 2 элементы типа char. Пары организованы в список типа TPairsList.
Основное меню, позволяет выбрать одну из следующих операций:
1. Ввести граф с клавиатуры;
2. Найти компоненты связности.
Выход из программы или возврат в главное меню происходит при нажатии клавиши Esc.
Матрица смежности строится из связанных вершин. Так как граф не является ориентированным, для удобства пользователя матрица смежности приводится к симметричной.
Поиск компонент связности производится при помощи рекурсивного алгоритма «поиск в глубину», которая за один проход находит одну компоненту связности, заполняя массив vec. Поиск повторяется, пока не будут отмечены все вершины.