Advertisement
Josif_tepe

Untitled

May 15th, 2022
515
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int n, m;
  5. vector<int> graph[1005];
  6. bool visited[1005], dfs_visited[1005];
  7.  
  8. bool dfs(int node) {
  9.     visited[node] = true;
  10.     dfs_visited[node] = true;
  11.    
  12.     for(int i = 0; i < graph[node].size(); i++) {
  13.         int sosed = graph[node][i];
  14.         if(!visited[sosed]) {
  15.             if(dfs(sosed)) {
  16.                 return true;
  17.             }
  18.         }
  19.         else if(dfs_visited[sosed]) {
  20.             return true;
  21.         }
  22.     }
  23.     dfs_visited[node] = false;
  24.     return false;
  25. }
  26. int main() {
  27.     cin >> n >> m;
  28.     memset(visited, false, sizeof visited);
  29.     memset(dfs_visited, false, sizeof dfs_visited);
  30.     for(int i = 0; i < m; i++) {
  31.         int a,b;
  32.         cin >> a >> b;
  33.         graph[a].push_back(b);
  34.     }
  35.     for(int i = 0; i < n; i++) {
  36.         if(!visited[i] and dfs(i)) {
  37.             cout << "DA" << endl;
  38.             return 0;
  39.         }
  40.     }
  41.     cout << "NE" << endl;
  42.     return 0;
  43. }
  44.  
Advertisement
RAW Paste Data Copied
Advertisement