Advertisement
Tranvick

Untitled

Mar 2nd, 2013
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None | 0 0
  1. #include <map>
  2. #include <set>
  3. #include <vector>
  4. #include <fstream>
  5. #include <iostream>
  6. #include <stack>
  7.  
  8. using namespace std;
  9.  
  10. map<int, vector<int> > graph;
  11. stack<int> st;
  12. set<int> used;
  13.  
  14. bool dfs(int S, int T) {
  15.     used.insert(S);
  16.     st.push(S);
  17.     while (!st.empty()) {
  18.         int v = st.top(); st.pop();
  19.         if (v == T) return true;
  20.         vector<int> & to = graph[v];
  21.         for (int i = 0; i < to.size(); ++i) if (!used.count(to[i])) {
  22.             used.insert(to[i]);
  23.             st.push(to[i]);
  24.         }
  25.     }
  26.     return false;
  27. }
  28.  
  29. int main() {
  30.     setlocale(LC_ALL, ".1251");
  31.     ifstream fin("input.txt");
  32.     int s, t, m;
  33.     fin >> m >> s >> t;
  34.     while (m--) {
  35.         int x, y;
  36.         fin >> x >> y;
  37.         graph[x].push_back(y);
  38.     }
  39.     cout << (dfs(s, t) ? "Да\n" : "Нет\n");
  40.     return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement