2360. Самый длинный цикл в графе (Longest Cycle in a Graph)

Задание.

Вам дается ориентированный граф из n узлов, пронумерованных от 0 до n - 1, где каждый узел имеет не более одного исходящего ребра.

Граф представлен заданным 0-индексированным массивом ребер размера n, указывающим на то, что существует направленное ребро от узла i к узлу edges[i]. Если нет исходящего ребра из узла i, то edges[i] == -1.

Верните длину самого длинного цикла на графе. Если цикл не существует, верните значение -1.

Цикл – это путь, который начинается и заканчивается в одном и том же узле.

Пример 1.

Входные данные: edges = [3,3,4,2,3]

Результат: 3

Пояснение: Самый длинный цикл графа – это цикл: 2 -> 4 -> 3 -> 2, поэтому возвращается число 3.

Пример 2.

Входные данные: edges = [2,-1,3,1]

Результат: -1

Пояснение: Граф не содержит циклов.

Решение.

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        
    }
};

Способ решения.

Обзор

Нам дан ориентированный граф с n узлами, пронумерованными от 0 до n - 1. Каждый узел имеет не более одного исходящего ребра, заданного edges.

Наша задача состоит в том, чтобы вернуть длину самого длинного цикла на графике. Если цикла не существует, нам нужно вернуть значение -1.

Способ 1. Dfs. Обход графа в глубину.

Интуиция

Проблема указывает на то, что каждый узел имеет не более одного исходящего ребра. Давайте посмотрим, какие типы графов мы можем создать с помощью этого.

Рассмотрим узел node, у которого есть цикл. Это означало бы, что единственное исходящее ребро узла также будет находиться в этом цикле. В результате узел не может быть частью какого-либо другого цикла, поскольку у него есть только одно исходящее ребро, которое используется в этом цикле. Это демонстрирует, что в графе только с одним исходящим ребром узел не может быть частью более чем одного цикла.