Sponsored
Sponsored
This approach utilizes the concept of reversing the graph and then performing a topological sort. Essentially, if we consider nodes leading to terminal nodes in the original graph, these nodes can be treated as terminal nodes in the reversed graph. We perform a topological sort to find such nodes.
By processing nodes which have no outgoing edges in the reversed graph (these correspond to safe nodes in the original graph), we can iteratively determine more nodes that are safe.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is due to the graph traversal.
Space Complexity: O(V) for storing the reversed graph and the in-degrees array.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5void findEventualSafeNodes(int** graph, int graphSize, int* graphColSize, int* returnSize) {
6 // Implementation
7}
8
9int main() {
10 int n = 7;
11 int graphColSize[] = {2, 2, 1, 1, 1, 0, 0};
12 int graphData[7][2] = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
13 int* graph[7];
14 for (int i = 0; i < 7; i++) {
15 graph[i] = graphData[i];
16 }
17 int returnSize = 0;
18 findEventualSafeNodes(graph, 7, graphColSize, &returnSize);
19 return 0;
20}The function findEventualSafeNodes reverses the input graph and employs a topological sorting method to determine the safe nodes.
For simplicity, you will need to manage node degrees and process the graph using a queue (BFS style). Nodes that have no incoming edges left are safe.
This approach adopts a classic depth-first search (DFS) to identify which nodes are safe. Safe nodes are marked during traversal.
We maintain a visited state for each node: unvisited, visiting, or safe. During DFS traversal, if we encounter a node marked as visiting, a cycle is detected, and the path is unsafe.
Time Complexity: O(V + E), as each node and each edge is examined only once.
Space Complexity: O(V) for the recursion stack and state storage.
1#include <vector>
2#include <iostream>
3using namespace std;
4
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
// Implementation
return {};
}
int main() {
vector<vector<int>> graph = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
vector<int> result = eventualSafeNodes(graph);
for (int node : result) {
cout << node << " ";
}
return 0;
}The function leverages DFS to maintain a status for each node: safe, unsafe, or unknown. It handles cycles efficiently by marking nodes actively being visited and recording safe nodes on successful completion of DFS for a node.