Advertisement
nq1s788

проверка на ацикличность

Mar 8th, 2025
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <deque>
  5.  
  6. using namespace std;
  7.  
  8. vector <vector<int>> g;
  9. vector<int> used;
  10. bool flag = false;
  11.  
  12. void dfs(int h, int p) {
  13.     used[h] = 1;
  14.     for (auto e : g[h]) {
  15.         if (used[e] == 1 && e != p) flag = true;
  16.         if (used[e] == 0) dfs(e, h);
  17.     }
  18.     used[h] = 2;
  19. }
  20.  
  21. int main() {
  22.     int n, m;
  23.     cin >> n >> m;
  24.     g.resize(n);
  25.     int x, y;
  26.     for (int i = 0; i < m;i++)
  27.     {
  28.         cin >> x >> y;
  29.         g[x - 1].push_back(y - 1);
  30.         g[y - 1].push_back(x - 1);
  31.     }
  32.     int start;
  33.     cin >> start;
  34.     used.assign(n, 0);
  35.     dfs(start - 1, -1);
  36.     if (flag) cout << "цикл есть";
  37.     else cout << "цикла нет";
  38.     return 0;
  39. }
  40.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement