fork(1) download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int ** a; // Матрица смежности будет записана именно сюда.
  6. int n = 51; // Число вершин.
  7. int* was;// Массив цвета вершины.
  8.  
  9. bool dfs(int key){
  10. //"Красим" вершину в серый цвет (указываем, что мы в нее вошли).
  11. was[key] = 1;
  12. //Проходим все связанные с текущей вершиной.
  13. for(int i = 0; i < n; i++){
  14. //Если значение элемента строки матрицы (по условию, нам дана матрица смежности) отлично от "0", то:
  15. if(a[key][i]){
  16. //если вершина "белая" (т. е. мы в неё еще не заходили)-
  17. //запускаем рекурсивный вызов DFS от этой вершины.
  18. if(was[i] == 0){if(dfs(i)) return true;}
  19. //если вершина "серая" (мы её уже навещали, но не возвращались из ее потомков)-
  20. //мы нашли цикл, следовательно поиск можно завершить.
  21. else if(was[i] == 1){ return true;}
  22. }
  23. }
  24. //Если ни один из if - ов не сработал, то "красим" вершину в черный цвет (отмечаем, как пройденную)
  25. was[key] = 2;
  26. //и возвращаем результат поиска (мы ничего не нашли).
  27. return false;
  28. }
  29. int main() {
  30. cin >> n;
  31. a = new int *[n];
  32. was = new int [n];
  33. for(int i = 0; i < n; i++){
  34. a[i] = new int [n];
  35. was[i] = 0;
  36. for(int j = 0; j < n; j++){
  37. cin >> a[i][j];
  38. }
  39. }
  40. for(int i = 0; i < n; i++){
  41. //Проверяем поиском каждую вершину. Если поиск оказался успешным - выводим "1".
  42. //Проверка цвета сделана ради ускорения процесса, иначе в поиске пришлось бы проходить весь
  43. //цикл, даже если вершина покрашена в черный цвет.
  44. if(!was[i]&&dfs(i)) {cout << "1\n"; return 0;}
  45. }
  46. //Если if ни разу не сработал - выводим "0".
  47. cout << "0\n";
  48. return 0;
  49. }
Success #stdin #stdout 0s 3276KB
stdin
Standard input is empty
stdout
0