Advertisement
Andre1314

Untitled

Sep 13th, 2023
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <set>
  5. #include <map>
  6. #include <queue>
  7.  
  8. using namespace std;
  9. #define pll pair<long,pair<long,long>>
  10.  
  11. long res = -1;
  12.  
  13. long rooms, arrows;
  14. long temp, temp2;
  15. vector<set<long>> a;
  16.  
  17. set<long> used;
  18.  
  19. bool dfs(long start, set<long> visited = {}) {
  20.     visited.insert(start);
  21.  
  22.     set<long> connections = a[start];
  23.  
  24.     for (auto connection : connections) {
  25.         if (visited.size() >= rooms-1) {
  26.             return true;
  27.         }
  28.  
  29.         if (visited.find(connection) == visited.end()) {
  30.             if (dfs(connection, visited)) return true;
  31.         }
  32.     }
  33.     return false;
  34. }
  35.  
  36. void main()
  37. {
  38.     cin >> rooms >> arrows;
  39.     a.resize(rooms);
  40.  
  41.     for (int i = 0; i < arrows; i++) {
  42.         cin >> temp >> temp2;
  43.         a[temp - 1].insert(temp2 - 1);
  44.     }
  45.  
  46.     for (int i = 0; i < rooms; i++) {
  47.         if (dfs(i)) res = i + 1;
  48.     }
  49.  
  50.     cout << res;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement