Advertisement
Josif_tepe

Untitled

Oct 17th, 2023
1,045
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5. vector<int> graph[maxn];
  6. int color[maxn];
  7. bool dfs(int node) {
  8.     color[node] = 1;
  9.    
  10.     for(int i = 0; i < (int) graph[node].size(); i++) {
  11.         int neighbour = graph[node][i];
  12.         if(color[neighbour] == 1) {
  13.             return true;
  14.         }
  15.         if(color[neighbour] == 0 and dfs(neighbour)) {
  16.             return true;
  17.         }
  18.     }
  19.     color[node] = 2;
  20.     return false;
  21. }
  22. int main() {
  23.     int n, m;
  24.     cin >> n >> m;
  25.    
  26.     for(int i = 0; i < m; i++) {
  27.         int a, b;
  28.         cin >> a >> b;
  29.         a--; b--;
  30.         graph[a].push_back(b);
  31.     }
  32.     for(int i = 0; i < n; i++) {
  33.         color[i] = 0;
  34.     }
  35.     for(int i = 0; i < n; i++) {
  36.         if(color[i] == 0) {
  37.             if(dfs(i)) {
  38.                 cout << "cycle" << endl;
  39.                 return 0;
  40.             }
  41.         }
  42.     }
  43.     cout << "no cycle" << endl;
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement