Find Eventual Safe States

Approach

In the Explanation section of the Problem Statement, you might have noticed that vertices that contain at least one cycle in their possible paths are not safe states. So, the given problem can be considered as a cycle detection problem. If none of the paths from the starting node contains a cycle, the starting node can be called a safe vertex. 

Method 1: BFS using Reverse Edges

If all the adjacent vertices from the starting vertex are safe states, then all the paths from the starting vertex can be considered safe. Why so? All the paths from a safe node are non-cyclic. So, if a vertex has safe states as adjacent vertices, all the paths from that vertex will be non-cyclic.

We know that terminal vertices are safe states too. So, we can start with terminal vertices and push them to our answer. From the terminal vertices, move up to the edges which are adjacent to the terminal vertices. This is what a typical breadth-first search algorithm behaves like.

How to do that? One way is to iterate through each vertex's adjacency list and check if the terminal vertex is adjacent to it. This is a very inefficient way, as an iteration through a graph requires O(nlogn) time at best(if adjacency lists are sorted).

Consider the graph given below:

Vertex 5 does not have any adjacent edges. The whole graph will be searched for edges for this vertex, and still, no next vertex will be found.

Is there any alternative for this process? Let’s create a reverse graph ‘R_GRAPH’. All the outgoing edges of the original graph ‘GRAPH’ will become incoming edges of the reverse graph ‘R_GRAPH’.

Let’s see how this reduces our time to find the adjacent edges of safe states. Look at the adjacency list representation of the graph given below.

Consider looking for the vertices that have vertex 5 as the adjacent vertex. Rather than iterating through the whole graph, we can check the adjacency list representation of ‘R_GRAPH’ for vertex 5. 

If a vertex is a safe vertex, we can remove its edges from other vertices. Why so?

Removing the edge from an adjacency list requires O(N) time, where ‘N’ is the number of elements in the list. To increase the efficiency of our method, we will use HashSet. HashSet can perform insertion and deletion operations in O(1). So, we will use a vector of HashSets to store adjacency sets of all the vertices of the graph.

Check all the adjacent edges of the current safe vertex in the ‘R_GRAPH’ and push them in the queue for future use. If the current vertex does not have any adjacent vertex in ‘GRAPH’, consider it as a safe vertex. After storing the adjacent vertices(from ‘R_GRAPH’) of a vertex in the queue, check if any of those vertices is a safe vertex. Refer to the algorithm given below for a better understanding.

Algorithm

• Set ‘N’ equal number of vertices.
• Initialize a boolean vector ‘SAFE’ of size ‘N’ with value false.
• Create a vector of HashSet ‘R_GRAPH’ and ‘GRAPH’ of size ‘N’.

• Create a queue ‘Q’ to store the safe states.
• Input values in the ‘GRAPH’ and ‘R_GRAPH’ using ‘INPUT’ graph. While filling the values if any of the vertex has no outgoing edges, push it into the queue.
• While ‘Q’ is not empty, do:
  • Initialize ‘CURRENT_VERTEX’ with the front element of the queue.
  • Remove the first element from the queue.
  • Set SAFE[CURRENT_VERTEX] = true (Vertex is present in the queue means it's safe).
  • Remove its edges with parents using rgraph.
  • If any of the parent has no outgoing edges in ‘GRAPH’ means it is safe node, then:
    • Push the parent into the queue ‘Q’.
• Return indices where SAFE[index] is true.

Program

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;

vector<int> eventualSafeStates(vector<vector<int>> &input)
{

    // Set 'N' equal number of vertices.
    int n = input.size();

    // Initialize a boolean vector 'SAFE' of size 'N' with value false.
    vector<int> safe(n, false);

    // Create a queue 'Q' to store the safe states.
    queue<int> q;

    // Create a vector of sets 'R_GRAPH' and 'graph' of size 'N'.
    vector<unordered_set<int>> graph(n), rGraph(n);

    for (int startVertex = 0; startVertex < n; startVertex++)
    {
        // If a vertex has no parent, push it into the queue.
        if (input[startVertex].size() == 0)
            q.push(startVertex);

        // Filling 'GRAPH' and 'R_GRAPH'.
        for (int endVertex: input[startVertex])
        {
            graph[startVertex].insert(endVertex);
            rGraph[endVertex].insert(startVertex);
        }
    }

    // Doing BFS on all the safe states.
    while (!q.empty())
    {
        int currentVertex = q.front();
        q.pop();

        // Vertex is present in the queue means it's safe.
        safe[currentVertex] = true;

        // Remove its edges with parents using rgraph.
        for (int parent : rGraph[currentVertex])
        {
            graph[parent].erase(currentVertex);

            // If any of the parent has no outgoing edges in 'GRAPH' means it is a safe node.
            if (graph[parent].size() == 0)
                q.push(parent);
        }
    }

    // 'ANSWER' vector to save vertex numbers of all the vertices.
    vector<int> answer;

    // Iterating through the 'SAFE' vector to check which of the vertices are marked safe.
    for (int i = 0; i < n; i++)
    {
        if (safe[i])
            answer.push_back(i);
    }
    return answer;
}

int main()
{

    // 'NUM_VERTICES' to store the total number of vertices in the graph.
    int numVertices;

    // 'ADJACENT' vertex to store the adjacent vertices of current vertex.
    int adjacent;
    cout << "Enter the number of vertices in the graph: ";
    cin >> numVertices;

    // 'GRAPH' vector to create adjacency list of the graph.
    vector<vector<int>> input(numVertices);

    cout << "Enter vertices adjacent to each vertex.\n";
    cout << "Enter -1 to move on to the next vertex.\n";

    for (int vertex = 0; vertex < numVertices; vertex++)
    {
        cout << "Vertex " << vertex << ": ";
        while (true)
        {
            cin >> adjacent;
            if (adjacent == -1)
                break;
            else
                input[vertex].push_back(adjacent);
        }
    }

    cout << "\nSafe states are: ";
    vector<int> safeVertices = eventualSafeStates(input);
    for (int safeVertex : safeVertices)
    {
        cout << safeVertex << " ";
    }
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the number of vertices in the graph: 7
Enter vertices adjacent to each vertex. 
Enter -1 to move on to the next vertex.
Vertex 0:    1     2    -1
Vertex 1:    2    3    -1
Vertex 2:    5    -1
Vertex 3:    0    -1
Vertex 4:    5    -1
Vertex 5:    -1
Vertex 6:    -1

Output

Safe states are:    2    4    5    6

Complexity Analysis

Time Complexity: O(N + E), where ‘N’ is the number of vertices in the given graph, and  ‘E’ is the total number of edges.

Space Complexity: Additional space is required to store the edges of the ‘R_GRAPH’. So, the space complexity is O(N + E), where ‘N’ is the number of vertices in the graph.

Method 2: DFS using Graph Coloring

During a depth-first search, a vertex can be in one of the three possible states: completely visited, unvisited, or being visited. A cycle is encountered when the dfs path leads to a vertex that is already being visited in the dfs path. 

In the figure given above, we can see the cycle is formed and confirm that vertices 1, 2, and  3 are not safe states. But for our DFS Algorithm function, we need to set some indicator that can represent whether the vertex is completely visited, unvisited, or being visited.

Let’s color code these vertices as follows to identify their state:

• White: Unvisited state.
• Black: Completely visited state.
• Gray: Being visited state.

The graph given above can be color-coded and may look like the figure given below.

So, for a dfs path, if any adjacent vertices are gray, we can call all the vertices of the path unsafe states.

Algorithm

• Set ‘WHITE’, ‘GRAY’, and ‘BLACK’ variables with values 0, 1, and 2.
• Initialize ‘COLORS’ vector to color code the vertices with ‘WHITE’ value.
• Declare an empty vector ‘SAFE_VERTICES’ to store the final result.
• Loop i variable through all the vertices, do:
  • If COLORS[i] is equal to ‘GRAY’, that means a cycle exists on one of the paths from the current vertex. So, it cannot be considered a safe node.
  • If COLORS[i] is equal to ‘BLACK’ it means it has undergone dfs without encountering a cycle. It can be considered a safe node. 
  • If dfs for current node is true, then:
    • Push the current node into  ‘SAFE_VERTICES’.
• Return ‘SAFE_VERTICES’.

Algorithm for DFS

• Let’s say the current dfs vertex is ‘VERTEX’.
• If COLORS[VERTEX] is not equal to ‘WHITE’, that means it is not an unvisited vertex.
  • If COLORS[VERTEX] is equal to ‘BLACK’, then:
    • Return true.
  • Else:
    • Return false.

Program

#include <iostream>
#include <vector>
using namespace std;

// Assigning every color with an integral value.
int white = 0, gray = 1, black = 2;

bool dfs(vector<vector<int>> &graph, vector<int> &colors, int vertex)
{

  /* 
      If current vertex is either completely visited or being visited,
      we do not need to call dfs on the current vertex.
  */
  if (colors[vertex] != white)
  {

    // If current vertex is being visited return false.
    // Else, return true.
    return colors[vertex] == black;
  }

  // Marking the current vertex as being visited before calling dfs on vertices adjacent to the current vertex.
  colors[vertex] = gray;

  // 'ADJ' variable represents adjacent vertex.
  for (int adj : graph[vertex])
  {

    // If the current adjacent vertex is already completely visited, it means it is already a safe vertex.
    if (colors[adj] == black)
      continue;

    // If adjacent vertex is being visited or the leading paths from the adjacent vertex return false, it means a cycle is encountered.
    if (colors[adj] == gray || !dfs(graph, colors, adj))
      return false;
  }

  // Coloring the current vertex black as all the adjacent vertices of current vertex are visited.
  colors[vertex] = black;

  // All the adjacent vertices of current vertex are safe states, so it can be called a safe vertex.
  return true;
}

vector<int> eventualSafeStates(vector<vector<int>> &graph)
{

  int numVertices = graph.size();

  // Initializing a 'COLORS' vector for the color codes of all vertices as unvisited.
  vector<int> colors(numVertices, white);

  // 'SAFE_VERTICES' vector to store all the safe states.
  vector<int> safeVertices;

  for (int i = 0; i < numVertices; i++)
  {

    // If the current vertex was not completely explored that means a cycle was found in one of its paths. So, it can not be considered as answer.
    if (colors[i] == gray)
      continue;

    // If the current vertex is already completely visited, it means it is already a safe vertex.
    if (colors[i] == black)
      safeVertices.push_back(i);
    else if (dfs(graph, colors, i))
      safeVertices.push_back(i);
  }

  return safeVertices;
}

int main()
{

  // 'NUM_VERTICES' to store the total number of vertices in the graph.
  int numVertices;

  // 'ADJACENT' vertex to store the adjacent vertices of current vertex.
  int adjacent;
  cout << "Enter the number of vertices in the graph: ";
  cin >> numVertices;

  // 'GRAPH' vector to create adjacency list of the graph.
  vector<vector<int>> graph(numVertices);

  cout << "Enter vertices adjacent to each vertex.\n";
  cout << "Enter -1 to move on to the next vertex.\n";

  for (int vertex = 0; vertex < numVertices; vertex++)
  {
    cout << "Vertex " << vertex << ": ";
    while (true)
    {
      cin >> adjacent;
      if (adjacent == -1)
        break;
      else
        graph[vertex].push_back(adjacent);
    }
  }

  cout << "\nSafe states are: ";
  vector<int> safeVertices = eventualSafeStates(graph);
  for (int safeVertex : safeVertices)
  {
    cout << safeVertex << " ";
  }
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the number of vertices in the graph: 7
Enter vertices adjacent to each vertex. 
Enter -1 to move on to the next vertex.
Vertex 0:    1     2    -1
Vertex 1:    2    3    -1
Vertex 2:    5    -1
Vertex 3:    0    -1
Vertex 4:    5    -1
Vertex 5:    -1
Vertex 6:    -1

Output

Safe states are:    2    4    5    6

Complexity Analysis

Time complexity: O(N + E), where ‘N’ represents the number of vertices, and ‘E’ is the total number of edges in the graph.

Space complexity: Additional space is required to store the colours of the vertices. So, the space complexity is O(N), where ‘N’ represents the number of vertices in the graph.

Check out this problem - Reverse Nodes In K Group

Key Takeaways

Congratulations on your learning! Finding Eventual Safe States is an interesting question, but it is not the only interesting question here. Find more interesting questions on our practice platform Coding Ninjas Studio. If you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!