Advertisement
VladimirKostovsky

С 19 с чем-то летием

May 30th, 2022
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include <fstream>
  4.  
  5. #define NODE 10
  6.  
  7. using namespace std;
  8. ofstream fout;
  9. ifstream fin;
  10.  
  11. int graph[NODE][NODE] = {
  12. {0, 1, 1, 1, 0, 0, 0, 0, 1, 0},
  13. {1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
  14. {1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
  15. {1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
  16. {0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
  17. {0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
  18. {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
  19. {0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
  20. {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  21. {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
  22. };
  23. int tempGraph[NODE][NODE];
  24.  
  25. int findStartVert() {
  26.     for (int i = 0; i < NODE; i++) {
  27.         int deg = 0;
  28.         for (int j = 0; j < NODE; j++) {
  29.             if (tempGraph[i][j])
  30.                 deg++; //степень увеличивается, когда обнаружен соединенный граф
  31.         }
  32.         if (deg % 2 != 0) //когда степень вершин нечетна
  33.             return i; //i - узел с нечетной степенью
  34.     }
  35.     return 0; //когда все вершины имеют четную степень, начинайте с 0
  36. }
  37. bool isBridge(int u, int v) {
  38.     int deg = 0;
  39.     for (int i = 0; i < NODE; i++)
  40.         if (tempGraph[v][i])
  41.             deg++;
  42.     if (deg > 1) {
  43.         return false; //край не образует перемычки
  44.     }
  45.     return true; //кромка, образующая перемычку
  46. }
  47. int edgeCount() {
  48.     int count = 0;
  49.     for (int i = 0; i < NODE; i++)
  50.         for (int j = i; j < NODE; j++)
  51.             if (tempGraph[i][j])
  52.                 count++;
  53.     return count; //подсчитываем количество ребер в графе
  54. }
  55. void fleuryAlgorithm(int start) {
  56.     static int edge = edgeCount();
  57.     for (int v = 0; v < NODE; v++) {
  58.         if (tempGraph[start][v]) { //когда (u, v) ребро присутствует и не образует перемычку
  59.             if (edge <= 1 || !isBridge(start, v)) {
  60.                 fout << start << "--" << v << " ";
  61.                 cout << start << "--" << v << " ";
  62.                 tempGraph[start][v] = tempGraph[v][start] = 0; //удаляем ребро из графика
  63.                 edge--; //уменьшаем ребро
  64.                 fleuryAlgorithm(v);
  65.             }
  66.         }
  67.     }
  68. }
  69. int main() {
  70.     fout.open("output.txt");
  71.     for (int i = 0; i < NODE; i++) //копируем основной график во временный график
  72.         for (int j = 0; j < NODE; j++)
  73.             tempGraph[i][j] = graph[i][j];
  74.     cout << "Cep` Eylera: ";
  75.     fleuryAlgorithm(findStartVert());
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement