Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <fstream>
- using namespace std;
- void zont(int**, int*, int*, int, int);
- int main()
- {
- setlocale(LC_ALL, "Russian");
- int N, M; // количество вершин и ребер
- int** a; // массив ребер
- int** v; // матрица
- ifstream in("D:\\Users\\Nevarkir\\source\\repos\\Project1\\Project1\\4e\\input.txt");
- in >> N; // ввод количества вершин
- in >> M; // ввод количества ребер
- // инициализация двумерного динамического массива
- a = new int* [M];
- for (int i = 0; i < M; i++)
- {
- a[i] = new int[2];
- }
- // инициализация двумерной динамической матрицы
- v = new int* [N];
- for (int i = 0; i < N; i++)
- {
- v[i] = new int[N];
- }
- // заполнение двумерного динамического массива
- for (int i = 0; i < M; i++)
- {
- for (int j = 0; j < 2; j++)
- {
- in >> a[i][j];
- }
- }
- in.close();
- // обнуление матрицы
- for (int i = 0; i < N; i++)
- {
- for (int j = 0; j < N; j++)
- {
- v[i][j] = 0;
- }
- }
- // занесение вершин в матрицу
- for (int i = 0; i < M; i++)
- {
- v[a[i][0] - 1][a[i][1] - 1] = 1;
- v[a[i][1] - 1][a[i][0] - 1] = 1;
- }
- // инициализация и обнуление массива для метки посещенных вершин
- int* b;
- b = new int[N];
- for (int i = 0; i < N; i++)
- {
- b[i] = 0;
- }
- int Z = N; // количество вершин которые нужно пройти, с каждой новой вершиной значение снижается
- int* zed = &Z; // указатель на количество вершин которые нужно пройти
- int Comp = 0; // количество компонентов связности
- int y = 0; // индекс обхода
- // массив работает до тех пор пока программа не пройдет каждую вершину
- while (*zed > 0) {
- zont(v, b, zed, N, y); // функция обхода одной компонент связности
- Comp++; // Увеличиваем количество компонент связности
- for (int i = 0; i < N; i++) // подбор следующего индекса с непосещенной вершиной
- {
- if (b[i] == 0) y = i;
- }
- }
- ofstream out;
- out.open("D:\\Users\\Nevarkir\\source\\repos\\Project1\\Project1\\4e\\output.txt");
- out << Comp << endl; // вывод количества компонент связности
- out.close();
- system("PAUSE");
- // освобождение памяти
- for (int i = 0; i < M; i++) {
- delete[] a[i];
- }
- delete[] a;
- for (int i = 0; i < N; i++) {
- delete[] v[i];
- }
- delete[] v;
- delete[] b;
- system("PAUSE");
- return 0;
- }
- void zont(int** A, int* B, int* Z, int N, int i)
- {
- bool solo = true; // метка чтобы определить компонент связности состоящих из одной вершины
- for (int j = 0; j < N; j++)
- {
- if (A[i][j] == 1)
- {
- solo = false; // если мы нашли связь с другой вершиной значит вершина не одиночка
- if ((B[j] == 0) && (B[i] == 0))
- {
- (*Z)--; // если обе точке ранее не посещались, то удаляем из
- (*Z)--; // количества вершин которые надо пройти сразу 2
- B[j] = 1; // отмечаем вершины
- B[i] = 1;
- zont(A, B, Z, N, j); // исследуем в глубину
- }
- else if ((B[j] == 0) && (B[i] == 1))
- {
- (*Z)--; // в этом случае посещалась только одна вершина, поэтому удаляем одну
- B[j] = 1;
- zont(A, B, Z, N, j);
- }
- }
- }
- if (solo == true)
- {
- (*Z)--; // если вершина без ребер то удаляем одну
- B[i] = 1; // отмечаем одинокую вершину
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement