Lesson_07/Task_4/Task_4.cpp - master - AirLexa/03

Lesson_07/Task_4/Task_4.cpp
79 строк3 KB
AirLexa
загрузил Lesson_07/Task_4/Task_4.cpp
23 янв 2026, 15:33
23 янв 2026, 15:3362e7b3b
#include <iostream>
#include <fstream>
#include <windows.h>

void visit(int n, bool** arr, bool* check, int* con, int size, int &num)
{
	check[n] = true; // посетили вершину
	con[n] = num; // записываем ее номер связности
	std::cout << " " << (n + 1); // выводим ее на экран
	for (int i = 0; i < size; i++) // пробегаем по ее ребрам
		if (arr[n][i] && !check[i]) visit(i, arr, check, con, size, num);
	// если есть ребро до следующей вершины и она еще 
	// не в списке посещенных, рекурсивно ее посещяем.
}

int main()
{
	SetConsoleCP(1251);
	SetConsoleOutputCP(1251);

	std::string name = "";
	std::cout << "Введите номер матрицы (1/2): ";
	std::cin >> name;
	name = "input_" + name + ".txt";
	std::ifstream file(name); // файл инициализации в папке с исполняемым файлом

	if (!file.is_open()) // проверка на доступ к файлу
	{
		std::cout << "Ошибка открытия файла: " << name << std::endl;
		return -1;
	}

	int size = 0;
	file >> size; // первая строчка - это размер массива
	if (size <= 1) // проверка на корректность значений размера
	{
		std::cout << "Ошибка! Количество вершин графа должно быть 2 или больше!" << std::endl;
		return -2;
	}
	// двухмерный массив
	bool** arr = new bool* [size]; // пользуемся тем, что 0 = false, !0 = true
	for (int i = 0; i < size; i++)
	{
		arr[i] = new bool[size]();
		for (int j = 0; j < size; j++) // заполняем массив данными
			file >> arr[i][j];
	}
	file.close(); // файл больше не понадобится

	std::cout << "Исходная матрица смежности:\n";
	for (int i = 0; i < size; i++) // выводим массив на консоль
	{
		for (int j = 0; j < size; j++)
			std::cout << arr[i][j] << " ";
		std::cout << std::endl;
	}

	std::cout << "Порядок обхода вершин:";
	bool* check = new bool[size](); // массив хранения посещенных вершин
	int* con = new int[size](); // массив хранения номеров связности
	int con_num = 0; // текущий номер связности
	
	for (int i = 0; i < size; i++) // обходим все непосещенные вершины
		if (!check[i]) visit(i, arr, check, con, size, ++con_num);
	
	std::cout << "\nПринадлежность вершин компонентам связности:\n";
	for (int i = 0; i < size; i++) // выводим массив на консоль
		std::cout << (i + 1) << " - " << con[i] << std::endl;
	std::cout << "Количество компонентов связности в графе: " 
		<< con[size - 1] << std::endl;

	for (int i = 0; i < size; i++) // освобождаем память
		delete[] arr[i];
	delete[] arr;
	delete[] check;
	delete[] con;

	return 0;
}