Advertisement
ke_timofeeva7

первая задача с дфс

Mar 12th, 2021
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <string>
  4. #include <sstream>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <memory.h>
  8. #include <stdio.h>
  9. #include <vector>
  10. #include <stack>
  11. #include <deque>
  12. #include <queue>
  13. #include <vector>
  14. #include <set>
  15. #include <iterator>
  16. #include <map>
  17. #define int long long
  18. #define sp system("pause")
  19. #define pb push_back
  20. #define endl '\n'
  21. using namespace std;
  22.  
  23. int mas[100][100]; // матрица смежности
  24. int mark[10000]; // массив с отметками, посещали мы вершину или нет
  25. vector <set<int>> gr(10000); // список смежности
  26. int ans = 0;
  27.  
  28. // функция перевода матрицы смежности в список смежности
  29. void in_set(int n)
  30. {
  31.     for (int i = 0; i < n; i++)
  32.     {
  33.         for (int j = 0; j < n; j++)
  34.         {
  35.             if (mas[i][j] == 1)
  36.             {
  37.                 gr[i].insert(j);
  38.             }
  39.         }
  40.     }
  41.  
  42.     return;
  43. }
  44.  
  45. // обход в глубину
  46.  
  47. void DFS(int v) // v - вершина, из которой рассматриваем дальнейшие вершины
  48. {
  49.     mark[v] = 1; // помечаем вершину, что мы в ней были
  50.  
  51.     for (int i : gr[v]) // идем по всем вершинам, куда можно попасть из v
  52.     {
  53.         if (mark[i] == 0) // если мы в вершине не были, то запускаем функцию оттуда
  54.         {
  55.             DFS(i);
  56.             ans++;
  57.         }
  58.     }
  59.  
  60.     return;
  61. }
  62. signed main()
  63. {
  64.     ios_base::sync_with_stdio(0);
  65.     cin.tie(0);
  66.     cout.tie(0);
  67.  
  68.     int n, s;
  69.     cin >> n >> s;
  70.  
  71.     // ввод матрицы смежности
  72.  
  73.     for (int i = 0; i < n; i++)
  74.     {
  75.         for (int j = 0; j < n; j++)
  76.         {
  77.             cin >> mas[i][j];
  78.         }
  79.     }
  80.  
  81.     // перевод матрицы в список смежности
  82.     in_set(n);
  83.  
  84.     // s -- вершина, из которой мы запускаем дфс изначально
  85.     s--;
  86.     DFS(s);
  87.  
  88.     cout << ans;
  89.  
  90.     return 0;
  91. }
  92.  
  93.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement