fork download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. enum color_t {
  6. WHITE, GRAY, BLACK // Вводим тип данных, отвечающий за цвет вершины
  7. };
  8.  
  9. vector<color_t> color; // Список, в котором указаны цвета всех вершин
  10. vector<vector<int>> crossroads; // Списки смежности перекрестков
  11.  
  12. bool is_track(int crossroad, int parent) { // Функция, проверяющая наличие круговой трассы
  13. if(color[crossroad] == GRAY) return true; // Условие существования цикла
  14. color[crossroad] = GRAY;
  15. for(auto next_crossroad : crossroads[crossroad]) { // Переход в соседние вершины
  16. if(parent != next_crossroad && is_track(next_crossroad, crossroad)) return true; // Вход в вершину, которую еще не входили
  17. }
  18. color[crossroad] = BLACK; // Если далее нет цикла, окрашиваем вершину в черный
  19. return false;
  20. }
  21.  
  22. int main() {
  23. int n, m; // Количество перекрестков и дорог
  24. cin >> n >> m;
  25. crossroads.resize(n);color.resize(n, WHITE); // Окрашиваем все вершины в белый цвет
  26. for(int i = 0; i < m; i++) {
  27. int u, v; // Номер перекрестков, соединенных дорогой
  28. cin >> u >> v;
  29. u--;v--; // Так как по условию отсчёт начинается с первой вершины, вычитаем 1 для удобства
  30. bool already_road = false; // Проверяем, не повторяется ли дорога
  31. if(!crossroads[u].empty() && !crossroads[v].empty()) {
  32. int number_of_neighbours = crossroads[u].size();
  33. for(int j = 0; j < number_of_neighbours && already_road == false; j++) {
  34. if(crossroads[u][j] == v) already_road = true;
  35. }
  36. }
  37. if(!(already_road)) { // Проверка на повторение
  38. crossroads[u].push_back(v); // Добавляем в список доступных перекрестков перекрестка u перекресток v
  39. crossroads[v].push_back(u); // Аналогичные действия для перекрестка v, чтобы учесть возможность двусторонней езды
  40. }
  41. }
  42. cout << (is_track(0, 0) ? "YES" : "NO"); // Запускаем функцию поиска круговой трассы с первого перекрестка и выводим ответ
  43. }
  44.  
Success #stdin #stdout 0s 4356KB
stdin
2 5
1 2
1 2
1 2
2 1
2 1
stdout
NO