Advertisement
Nikmosi

tg pz 1 ex 8

Apr 3rd, 2021
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <queue>
  5. #include <set>
  6.  
  7. bool has_path_dfs(const std::vector<std::vector<int>> &gr, int fr, int to, std::set<int> &gray)
  8. {
  9.     if (fr == to) return true;
  10.     gray.insert(fr);
  11.     for (int j : gr[fr])
  12.     {
  13.         if (gray.count(j) != 0) continue;
  14.         if (has_path_dfs(gr, j, to, gray)) return true;
  15.     }
  16.     return false;
  17. }
  18.  
  19.  
  20.  
  21. bool has_path_bfs(const std::vector<std::vector<int>> &gr, int fr, int to)
  22. {
  23.     auto *q = new std::queue<int>();
  24.     q->push(fr);
  25.     auto *gray = new std::set<int>();
  26.     while (!q->empty())
  27.     {
  28.         int v = q->front();
  29.         q->pop();
  30.         gray->insert(v);
  31.         for (int j : gr[v])
  32.         {
  33.             if (gray->count(j) == 0) q->push(j);
  34.             if (j == to) return true;
  35.         }
  36.     }
  37.  
  38.     return false;
  39. }
  40.  
  41. int main(int argc, char *argv[])
  42. {
  43.     auto *input = new std::ifstream("input.txt");
  44.     if (input)
  45.     {
  46.         int n, m;
  47.         *input >> n >> m;
  48.         std::vector<std::vector<int>> gr(n);
  49.         for (int i = 0; i < m; ++i)
  50.         {
  51.             int a, b;
  52.             *input >> a >> b;
  53.             gr[a].push_back(b);
  54.             gr[b].push_back(a);
  55.         }
  56.         std::set<int> bb;
  57.         std::cout << has_path_dfs(gr, 1, 4, bb) << std::endl;
  58.     }
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement