Advertisement
keymasterviriya1150

261

Apr 17th, 2021
990
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <queue>
  3. using namespace std;
  4. struct edge
  5. {
  6.     int to;
  7.     long long w;
  8.     edge(int a, long long b) : to(a), w(b) {}
  9.     bool operator<(const edge &o) const
  10.     {
  11.         return w > o.w;
  12.     }
  13. };
  14.  
  15. typedef vector<vector<edge>> graph;
  16. graph adj;
  17. vector<bool> visited;
  18.  
  19. bool dfsConnected(int s,int d,int n)
  20. {
  21.     if(s == d)
  22.         return true;
  23.     vector<int> vec;
  24.     visited.assign(n, false);
  25.     visited[s] = true;
  26.     vec.push_back(s);
  27.     while (!vec.empty()){
  28.         s= vec.front();
  29.         vec.erase(vec.begin());
  30.         for (auto &u : adj[s]){
  31.             if(u.to==d) return true;
  32.             if(!visited[u.to]){
  33.                 visited[u.to] = true;
  34.                 vec.push_back(u.to);
  35.             }
  36.         }
  37.        
  38.     }
  39.     return false;
  40. }
  41.  
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.     int n, m;
  47.     cin >> n >> m;
  48.     adj.resize(n+1);
  49.     for (int i = 0; i < m; i++)
  50.     {
  51.         int u, v;
  52.         cin >> u >> v;
  53.         adj[u].push_back({v, 0});
  54.     }
  55.     int q;
  56.     cin >> q;
  57.     int s,d;
  58.     while(q--){
  59.         cin >> s >> d;
  60.         if (dfsConnected(s, d,m))
  61.             cout << "yes" << endl;
  62.         else
  63.             cout << "no" << endl;
  64.     }
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement