Find Eventual Safe States

class Solution {
public:
    bool cycleDetected(int curr, vector<vector<int>>& graph, vector<bool>& visited,
             vector<bool>& recursionStack) {
        if (recursionStack[curr]) {
            return true;
        }
        if (visited[curr]) {
            return false;
        }
        visited[curr] = true;
        recursionStack[curr] = true;
        for (int next : graph[curr]) {
            if (cycleDetected(next, graph, visited, recursionStack)) {
                return true;
            }
        }
        recursionStack[curr] = false;
        return false;
    }

    vector<int> findSafeNodes(vector<vector<int>>& graph) {
        int totalNodes = graph.size();
        vector<bool> visited(totalNodes), recursionStack(totalNodes);

        for (int i = 0; i < totalNodes; i++) {
            cycleDetected(i, graph, visited, recursionStack);
        }

        vector<int> safeNodesList;
        for (int i = 0; i < totalNodes; i++) {
            if (!recursionStack[i]) {
                safeNodesList.push_back(i);
            }
        }

        return safeNodesList;
    }
};

In the provided C++ solution for identifying eventual safe states in a directed graph, the code follows a two-step approach:

1. Detect cycles within the graph using a modified depth-first search (DFS):

   • Implement a cycleDetected function that checks if any cycles are present starting from a specific node. It utilizes two vectors to track visited nodes and the call stack (recursionStack) to identify back edges, which signify a cycle.
   • The function returns true when a cycle is detected and false otherwise.

2. Identify and list all safe nodes:

   • A node is defined as "safe" if no cycles can be reached starting from this node.
   • After cycling through all nodes with the cycleDetected function, inspect each node. Nodes that don't have any active recursionStack marks (indicating that the node does not contribute to a cycle) are added to the safeNodesList.

The logic for cycle detection within the graph is critical in filtering out unsafe states, ensuring only truly safe states are added to the resulting list. This approach ensures computational efficiency and correctness in identifying safe states.

class Solution {

    public boolean cycleCheck(
        int currentNode,
        int[][] adjacencyList,
        boolean[] visited,
        boolean[] recursionStack
    ) {
        if (recursionStack[currentNode]) {
            return true; // Cycle found.
        }
        if (visited[currentNode]) {
            return false; // Already processed node.
        }
        visited[currentNode] = true;
        recursionStack[currentNode] = true;
        for (int adjacentNode : adjacencyList[currentNode]) {
            if (cycleCheck(adjacentNode, adjacencyList, visited, recursionStack)) {
                return true;
            }
        }
        recursionStack[currentNode] = false;
        return false;
    }

    public List<Integer> findSafeNodes(int[][] matrix) {
        int numVertices = matrix.length;
        boolean[] visited = new boolean[numVertices];
        boolean[] recursionStack = new boolean[numVertices];

        for (int vertex = 0; vertex < numVertices; vertex++) {
            cycleCheck(vertex, matrix, visited, recursionStack);
        }

        List<Integer> safeNodesList = new ArrayList<>();
        for (int vertex = 0; vertex < numVertices; vertex++) {
            if (!recursionStack[vertex]) {
                safeNodesList.add(vertex);
            }
        }

        return safeNodesList;
    }
}

This Java solution is designed to determine eventual safe states in a directed graph represented by an adjacency matrix. The central idea hinges on detecting cycles in the graph, as nodes that are part of cycles are not considered safe.

Key Procedure:

1. Helper Method (cycleCheck)

   • This method uses Depth First Search (DFS) to explore nodes and check for cycles.
   • Maintains two boolean arrays, visited and recursionStack. visited tracks whether a node has been checked, and recursionStack keeps track of nodes currently in the recursion stack (DFS path).
   • Returns true if a cycle is detected; otherwise, it returns false.

2. Main Method (findSafeNodes)

   • Initializes arrays to keep track of visited nodes and nodes in the recursion stack.
   • Iterates over each vertex and runs the cycleCheck for each one.
   • Constructs a list of safe nodes, i.e., nodes that are not part of any cycle. Nodes not in the recursion stack after checking are considered safe.

• At the conclusion of this approach:
  • The code systematically identifies nodes without any outgoing cycles as safe.
  • These safe nodes are accumulated in a List<Integer> and returned.

This solution adeptly combines graph traversal techniques with cycle detection to flag unsafe nodes efficiently, aligning well with explorations of state safety in graph structures.

class Solution:
    def depthFirstSearch(self, current, connections, visited, recursionStack):
        if recursionStack[current]:
            return True
        if visited[current]:
            return False
        visited[current] = True
        recursionStack[current] = True
        for next_node in connections[current]:
            if self.depthFirstSearch(next_node, connections, visited, recursionStack):
                return True
        recursionStack[current] = False
        return False

    def findSafeNodes(self, graph: List[List[int]]) -> List[int]:
        total_nodes = len(graph)

        visited = [False] * total_nodes
        recursionStack = [False] * total_nodes

        for index in range(total_nodes):
            self.depthFirstSearch(index, graph, visited, recursionStack)

        safeNodesList = []
        for index in range(total_nodes):
            if not recursionStack[index]:
                safeNodesList.append(index)

        return safeNodesList

The solution revolves around determining safe nodes in a directed graph where a node is termed 'safe' if it does not partake in any cycles. It employs the depth-first search (DFS) method to detect cycles efficiently. Here’s a step-by-step breakdown of the given code logic written in Python:

1. Define a depthFirstSearch method:

   • Checks for cycle presence when traversing through each node's connections.
   • Uses a recursion stack to manage the recursive depth of nodes being visited.
   • Marks nodes as visited to prevent redundant checks.
   • If a cycle is detected during traversal, it returns True, signaling an unsafe node.

2. Define a findSafeNodes method:

   • Initialize arrays visited and recursionStack to keep track of visited nodes and the nodes currently in the recursion stack, respectively.
   • Iterate over each node and apply the depthFirstSearch method to identify whether any node is part of a cycle using the stack-based cycle detection.
   • After validating all nodes, iterate through the recursionStack to collect nodes that are not part of any recursion (hence not in a cycle) and append them to safeNodesList.

The returned safeNodesList contains indices of all the nodes which can be classified as safe, meaning there's no path originating from these nodes that leads to a cycle.