Advertisement
r1411

боже что это

Jun 16th, 2021
776
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int a[100][100] = { 0 };
  5. int b[100][100] = { 0 };
  6. int num[100] = { 0 };
  7. int visit[100] = { 0 };
  8. int svaz[100] = { 0 };
  9. int n;
  10.  
  11. //ksv - номер компоненты связности
  12. void dfsNum(int m[100][100], int v, int k, int ksv) {
  13.     if (visit[v] == 0) {
  14.         visit[v] = 1;
  15.         num[v] = k;
  16.         svaz[v] = ksv;
  17.         cout << "Vertex " << v << " #" << k << "; KSV: " << ksv << endl;
  18.         for (int i = 1; i <= n; i++) {
  19.             if(m[v][i] == 1)
  20.                 dfsNum(m, i, k + 1, ksv);
  21.         }
  22.     }
  23. }
  24.  
  25.  
  26. void main() {
  27.     setlocale(LC_ALL, "Russian");
  28.  
  29.     cout << "Кол-во вершин: ";
  30.     cin >> n;
  31.  
  32.     int v1, v2;
  33.     cin >> v1 >> v2;
  34.     while (v1 != 0 && v2 != 0) {
  35.         a[v1][v2] = 1;
  36.         cin >> v1 >> v2;
  37.     }
  38.  
  39.     //сразу транспонируем a в b:
  40.     for (int i = 1; i <= n; i++)
  41.         for (int j = 1; j <= n; j++)
  42.             b[i][j] = a[j][i];
  43.  
  44.  
  45.     int maxN = 1;
  46.     int maxI = 1;
  47.     int ksv = 1;
  48.  
  49.     do {
  50.         dfsNum(a, 1, maxN, ksv);
  51.  
  52.         for (int i = 1; i <= n; i++) {
  53.             if (num[i] > maxN) {
  54.                 maxN = num[i];
  55.                 maxI = i;
  56.             }
  57.         }
  58.  
  59.         dfsNum(b, maxI, maxN + 1, ksv);
  60.        
  61.         ksv += 1;
  62.         maxI += 1;
  63.     } while (maxN < n);
  64.  
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement