Advertisement
Mirbek

Есть ли цикл?

Jan 9th, 2022
1,007
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 105;
  6.  
  7. int n;
  8. int used[N];
  9. int a[N][N];
  10. bool cycle = false;
  11.  
  12. void dfs(int v, int start) {
  13.     used[v] = 1;
  14.     for (int i = 1; i <= n; i++) {
  15.         if (a[v][i] == 1 && i == start) {
  16.             cycle = true;
  17.         }
  18.         if (a[v][i] == 1 && used[i] == 0) {
  19.             dfs(i, start);
  20.         }
  21.     }
  22. }
  23.  
  24. int main(){
  25.     cin >> n;
  26.  
  27.     for (int i = 1; i <= n; i++) {
  28.         for (int j = 1; j <= n; j++) {
  29.             cin >> a[i][j];
  30.         }
  31.     }
  32.  
  33.     for (int i = 1; i <= n; i++) {
  34.         for (int j = 1; j <= n; j++) {
  35.             used[j] = 0;
  36.         }
  37.         dfs(i, i);
  38.     }
  39.  
  40.     cout << cycle << endl;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement