Advertisement
Nevarkir

4E

Dec 7th, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <fstream>
  4.  
  5. using namespace std;
  6.  
  7. void zont(int**, int*, int*, int, int);
  8.  
  9. int main()
  10. {
  11.     setlocale(LC_ALL, "Russian");
  12.     int N, M; // количество вершин и ребер
  13.     int** a; // массив ребер
  14.     int** v; // матрица
  15.     ifstream in("D:\\Users\\Nevarkir\\source\\repos\\Project1\\Project1\\4e\\input.txt");
  16.     in >> N; // ввод количества вершин
  17.     in >> M; // ввод количества ребер
  18.  
  19.     // инициализация двумерного динамического массива
  20.     a = new int* [M];
  21.     for (int i = 0; i < M; i++)
  22.     {
  23.         a[i] = new int[2];
  24.     }
  25.  
  26.     // инициализация двумерной динамической матрицы
  27.     v = new int* [N];
  28.     for (int i = 0; i < N; i++)
  29.     {
  30.         v[i] = new int[N];
  31.     }
  32.  
  33.     // заполнение двумерного динамического массива
  34.     for (int i = 0; i < M; i++)
  35.     {
  36.         for (int j = 0; j < 2; j++)
  37.         {
  38.             in >> a[i][j];
  39.         }
  40.     }
  41.     in.close();
  42.     // обнуление матрицы
  43.     for (int i = 0; i < N; i++)
  44.     {
  45.         for (int j = 0; j < N; j++)
  46.         {
  47.             v[i][j] = 0;
  48.         }
  49.     }
  50.     // занесение вершин в матрицу
  51.     for (int i = 0; i < M; i++)
  52.     {
  53.         v[a[i][0] - 1][a[i][1] - 1] = 1;
  54.         v[a[i][1] - 1][a[i][0] - 1] = 1;
  55.     }
  56.     // инициализация и обнуление массива для метки посещенных вершин
  57.     int* b;
  58.     b = new int[N];
  59.     for (int i = 0; i < N; i++)
  60.     {
  61.         b[i] = 0;
  62.     }
  63.     int Z = N; // количество вершин которые нужно пройти, с каждой новой вершиной значение снижается
  64.     int* zed = &Z; // указатель на количество вершин которые нужно пройти
  65.     int Comp = 0; // количество компонентов связности
  66.     int y = 0; // индекс обхода
  67.     // массив работает до тех пор пока программа не пройдет каждую вершину
  68.     while (*zed > 0) {
  69.         zont(v, b, zed, N, y); // функция обхода одной компонент связности
  70.         Comp++; //  Увеличиваем количество компонент связности
  71.         for (int i = 0; i < N; i++) // подбор следующего индекса с непосещенной вершиной
  72.         {
  73.             if (b[i] == 0) y = i;
  74.         }
  75.     }
  76.     ofstream out;
  77.     out.open("D:\\Users\\Nevarkir\\source\\repos\\Project1\\Project1\\4e\\output.txt");
  78.     out << Comp << endl; // вывод количества компонент связности
  79.     out.close();
  80.     system("PAUSE");
  81.     // освобождение памяти
  82.     for (int i = 0; i < M; i++) {
  83.         delete[] a[i];
  84.     }
  85.     delete[] a;
  86.     for (int i = 0; i < N; i++) {
  87.         delete[] v[i];
  88.     }
  89.     delete[] v;
  90.     delete[] b;
  91.     system("PAUSE");
  92.     return 0;
  93. }
  94.  
  95. void zont(int** A, int* B, int* Z, int N, int i)
  96. {
  97.     bool solo = true; // метка чтобы определить компонент связности состоящих из одной вершины
  98.     for (int j = 0; j < N; j++)
  99.     {
  100.         if (A[i][j] == 1)
  101.         {
  102.             solo = false; // если мы нашли связь с другой вершиной значит вершина не одиночка
  103.             if ((B[j] == 0) && (B[i] == 0))
  104.             {
  105.                 (*Z)--; // если обе точке ранее не посещались, то удаляем из
  106.                 (*Z)--; // количества вершин которые надо пройти сразу 2
  107.                 B[j] = 1; // отмечаем вершины
  108.                 B[i] = 1;
  109.                 zont(A, B, Z, N, j); // исследуем в глубину
  110.             }
  111.             else if ((B[j] == 0) && (B[i] == 1))
  112.             {
  113.                 (*Z)--; // в этом случае посещалась только одна вершина, поэтому удаляем одну
  114.                 B[j] = 1;
  115.                 zont(A, B, Z, N, j);
  116.             }
  117.         }
  118.     }
  119.     if (solo == true)
  120.     {
  121.         (*Z)--; // если вершина без ребер то удаляем одну
  122.         B[i] = 1; // отмечаем одинокую вершину
  123.     }
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement