MiddleКодИногдаЕщё не отвечали
Найдите циклы и недоступные вершины в ориентированном графе
Проанализируйте ориентированный граф, заданный списком смежности. Реализуйте hasCycle и unreachable (вершины, недостижимые из набора источников).
Требования:
обратное ребро в серую вершину — это цикл. Простого флага visited мало.
компоненты.
- Обнаружение цикла за O(V+E): трёхцветный DFS (белый / серый / чёрный);
- Запускайте DFS от каждой непосещённой вершины, чтобы охватить несвязные
unreachable: DFS/BFS от всех источников, затем соберите непосещённые вершины.
class Graph {
public:
explicit Graph(int n) : adj_(n), n_(n) {}
void addEdge(int u, int v) { adj_[u].push_back(v); }
bool hasCycle() const {
// ваш код здесь
}
std::vector<int> unreachable(const std::vector<int>& sources) const {
// ваш код здесь
}
private:
std::vector<std::vector<int>> adj_;
int n_;
};Допишите реализацию.
Используйте DFS с трёхцветной пометкой: белый (непосещённый), серый (в текущем пути), чёрный (полностью обработан). Обратное ребро (серый→серый) указывает на цикл. Недоступные узлы остаются белыми после полного DFS от всех исходных вершин. Deadlock-состояние — это цикл в графе зависимостей/ожидания.
- ✗Использовать только множество посещённых — оно обнаруживает посещённые, но не обратные рёбра (в пути vs полностью обработан)
- ✗Не выполнять DFS от всех непосещённых вершин — пропускает несвязные компоненты
- ✗Путать обнаружение цикла в неориентированном графе (union-find) с ориентированным (цвета DFS)
- →Как топологическая сортировка связана с обнаружением циклов в DAG?
- →Что такое алгоритм Тарьяна для нахождения сильно связных компонент?
Оглавление
Задача
Реализуйте анализ ориентированного графа: обнаружение циклов и недоступных вершин (от заданных начальных вершин).
Решение
#include <vector>
#include <unordered_set>
#include <functional>
#include <cassert>
class Graph {
public:
explicit Graph(int n) : adj_(n), n_(n) {}
void addEdge(int u, int v) { adj_[u].push_back(v); }
// Обнаружение цикла через 3-цветной DFS
// 0 = белый, 1 = серый (в пути), 2 = чёрный (готов)
bool hasCycle() const {
std::vector<int> color(n_, 0);
bool found = false;
std::function<void(int)> dfs = [&](int u) {
if (found) return;
color[u] = 1; // серый
for (int v : adj_[u]) {
if (color[v] == 1) { found = true; return; } // back edge
if (color[v] == 0) dfs(v);
}
color[u] = 2; // чёрный
};
for (int i = 0; i < n_; ++i) if (color[i] == 0) dfs(i);
return found;
}
// Недоступные вершины (от набора источников)
std::vector<int> unreachable(const std::vector<int>& sources) const {
std::vector<bool> visited(n_, false);
std::function<void(int)> dfs = [&](int u) {
visited[u] = true;
for (int v : adj_[u]) if (!visited[v]) dfs(v);
};
for (int s : sources) if (!visited[s]) dfs(s);
std::vector<int> result;
for (int i = 0; i < n_; ++i) if (!visited[i]) result.push_back(i);
return result;
}
private:
std::vector<std::vector<int>> adj_;
int n_;
};
int main() {
// Граф с циклом: 0→1→2→0
Graph g1(3);
g1.addEdge(0, 1); g1.addEdge(1, 2); g1.addEdge(2, 0);
assert(g1.hasCycle());
// DAG: 0→1→2
Graph g2(3);
g2.addEdge(0, 1); g2.addEdge(1, 2);
assert(!g2.hasCycle());
// Недоступные: 0→1, вершина 2 недоступна
Graph g3(3);
g3.addEdge(0, 1);
auto unr = g3.unreachable({0});
assert(unr == std::vector<int>{2});
}Ключевые моменты
| Задача | Алгоритм | Сложность |
|---|---|---|
| Обнаружение цикла (ориент.) | DFS 3-цвет | O(V+E) |
| Недоступные вершины | DFS/BFS от источников | O(V+E) |
| Deadlock (wait-for граф) | Обнаружение цикла | O(V+E) |
Оглавление
