▲

3

▼

🚀 Определение безопасных вершин в графе с использованием DFS и состояний узлов

leetcoder, изменено 28-01-2025 , 440

В очередной задаче для обзора - 802. Find Eventual Safe States нам предстоит найти вершины, не попадающие в циклы графа.

📋 Описание задачи

Нужно определить безопасные вершины в ориентированном графе.

• Безопасная вершина — это такая вершина, из которой невозможно попасть в цикл. Если из вершины можно попасть только в терминальные вершины или другие безопасные, она считается безопасной.
• Граф представлен в виде списка смежности, где graph[i] содержит все вершины, в которые можно попасть из вершины i.
• Вернуть необходимо список всех безопасных вершин в возрастающем порядке.
  
• Граф из примера имеет безопасными вершины: [4,5,6]

💡 Идея

Задача решается с помощью обхода графа в глубину (DFS) и вектора состояний.
Каждому узлу присваивается одно из трёх состояний:

1. Unseen (ещё не обработан);
2. Processing (в процессе обработки; узлы, являющиеся частью цикла, остаются в этом состоянии и после обработки);
3. Safe (безопасный).

🔍 Детальное описание подхода

1. Инициализация состояний:
   • Каждый узел изначально находится в состоянии Unseen.
2. Реализация DFS:
   • При посещении узла он помечается как Processing, чтобы отметить, что он в процессе обработки.
   • Рекурсивно проверяются все соседи узла:
     • Если сосед ещё не обработан (Unseen), запускается его обработка через DFS.
     • Если сосед находится в состоянии Processing, это указывает на цикл, и текущий узел считается небезопасным.
     • Если сосед уже безопасен (Safe), проверка продолжается.
   • Если все соседи узла безопасны, узел помечается как Safe.
3. Сбор безопасных узлов:
   • После завершения обработки всех узлов, те из них, которые находятся в состоянии Safe, добавляются в результат.

📊 Асимптотика

• Время: O(V + E), где V — количество вершин, E — количество рёбер. Каждый узел и каждое ребро обрабатываются ровно один раз.
• Память: O(V) — для массива node_state и стека рекурсии.

💻 Исходный код

#[derive(Copy, Clone, PartialEq)]
enum NodeState {
    Unseen,
    Processing,
    Safe,
}

impl Solution {
    pub fn eventual_safe_nodes(graph: Vec<Vec<i32>>) -> Vec<i32> {
        let n = graph.len();
        let mut node_state = vec![NodeState::Unseen; n]; // Track the state of each node

        // Filter nodes that are determined to be safe
        (0..n)
            .filter(|&i| Self::dfs(i, &graph, &mut node_state))
            .map(|i| i as i32)
            .collect()
    }

    fn dfs(node: usize, graph: &[Vec<i32>], node_state: &mut [NodeState]) -> bool {
        if NodeState::Unseen == node_state[node] {
            node_state[node] = NodeState::Processing; // Mark the node as being processed

            // Check all neighbors
            for &neighbor in &graph[node] {
                let neighbor = neighbor as usize;
                // If any neighbor is unsafe, the current node is unsafe
                if !Self::dfs(neighbor, graph, node_state) {
                    return false;
                }
            }

            // Mark the node as safe after processing all neighbors
            node_state[node] = NodeState::Safe;
        }
        // Return true if the node is safe
        matches!(node_state[node], NodeState::Safe)
    }
}

Tags:  #rust #algorithms #graph #dfs