Ежедневный бит (е) C ++ # 203, Распространенная проблема на собеседовании: самый длинный цикл в графе.
Сегодня мы рассмотрим распространенную проблему интервью C++: самый длинный цикл в графе.
Для заданного ориентированного графа в виде std::vector‹int›, где значение в индексе i представляет пункт назначения исходящего ребра из i ( -1 используется для обозначения отсутствия исходящих ребер), определяют размер самого длинного цикла в графе.
Например, приведенный выше граф представлен {1,2,3,1,0}, образуя цикл размера три.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/4P3Pv8r9M.
Решение
Мы можем разбить задачу на две части: поиск циклов и определение размера наибольшего цикла.
Чтобы найти циклы в ориентированном графе, мы можем использовать алгоритм топологической сортировки, который работает за O(n), обрабатывая все узлы, не являющиеся частью цикла, оставляя нам циклы.
После того как мы выполнили топологическую сортировку, мы можем пройти каждый оставшийся цикл, подсчитывая количество узлов в этом цикле (также O(n)).
int longest_cycle(std::vector<int64_t>& edges) {
// Topological sort
// 1. Count incoming edges.
std::vector<int> incoming(edges.size(), 0);
for (auto v : edges)
if (v >= 0)
++incoming[v];
// 2. Start with nodes with zero incoming edges.
std::queue<int64_t> pending;
for (int64_t i = 0; i < std::ssize(edges); ++i)
if (incoming[i] == 0)
pending.push(i);
// 3. Process until we have no unprocessed nodes
// with zero incoming edges.
while (!pending.empty()) {
int64_t idx = pending.front();
pending.pop();
// No outgoing edges.
if (edges[idx] == -1) continue;
// Remove this edge.
--incoming[edges[idx]];
// If we created a node with zero incoming edges,
// add it to the queue.
if (incoming[edges[idx]] == 0)
pending.push(edges[idx]);
}
// At this point, all nodes that are not part of
// a cycle have zero incoming edges.
int max = -1;
// Traverse all cycles:
for (int64_t i = 0; i < std::ssize(edges); ++i) {
if (incoming[i] == 0) continue;
// 1. This is a node on a cycle.
--incoming[i];
int64_t idx = edges[i];
int sz = 1;
// 2. Traverse the cycle
while (idx != i) {
--incoming[idx];
idx = edges[idx];
++sz;
}
// 3. Keep track of the longest cycle.
max = std::max(max, sz);
}
return max;
}
