e-olimp 4004. Есть ли цикл?

Задача:

  Дан ориентированный граф. Требуется определить, есть ли в нём цикл.

Технические условия:

Входные данные:

В первой строке вводится натуральное число [latex]N ( N \leq 50)[/latex] — количество вершин. Далее в [latex]N[/latex] строках следуют по [latex]N[/latex] чисел, каждое из которых — «0» или «1«. [latex]j [/latex] -е число в [latex]i[/latex] -й строке равно «1» тогда и только тогда, когда существует ребро, идущее из [latex]i[/latex] -й вершины в [latex]j[/latex]-ю. Гарантируется, что на диагонали матрицы будут стоять нули.

Выходные данные:

Выведите «0«, если в заданном графе цикла нет, и «1«, если он есть.

Результат на С++

Результат на Java

Код на С++:

Код на Java:

 

Пояснение:

Циклом в графе называется цепь, в которой первая и последняя вершина совпадает. Значит, если проходя по вершинам графа в лексикографическом порядке, в какой — то момент я попаду в вершину в которую вошел, но еще не вышел, то это будет означать, что я нашёл цикл.

Если б мне по условию давался связный ориентированный граф, то достаточно было бы запустить поиск (поиск в глубину) из произвольной вершины и, по идее, мы бы обошли весь граф. Так как о связности графа ничего сказано не было, пришлось запускать поиск из каждой вершины.

4 thoughts on “e-olimp 4004. Есть ли цикл?

  1. Уточните, пожалуйста, что вы имеете в виду под «по вершинам графа в лексикографическом порядке».
    Начинать поиск с каждой вершины излишне. Если предыдущий поиск не дал цикла, то все пройденные вершины ни в какой цикл войти не могут.

  2. Я имел в виду, что я прохожу вершины в цикле от 0 — ой до n-1 — ой, т. е. я прохожу вершины в порядке возрастания их номеров.
    Я не мог быть уверен на счет числа компонент связности. По этой причине я не могу запускать поиск только из одной вершины, но я вставил в условие проверку «цвета» данной вершины, таким образом, в цикле программа будет пропускать уже посещенные вершины, а значит отсекать пройденную компоненту связности.

  3. Согласен. Зачтено
    Только поправьте:
    — вектор was на самом деле просто массив из n элементов (т.е. вектор вам ненужен)
    — нужна ссылка на задачу на сайте e-olimp.
    — код программы на этой странице и по ссылке в ideone не совпадает

Добавить комментарий