No one reveals how this works Find eventual safe states with a super dooper Kahn’s algorithm

Title Card

Introduction:

Thanks for your support, I’m 200% sure today you are going to learn something new let’s take one more shot with Kahn’s let’s break out what they are expecting from us, how will this work with sooper dooper visual as usual, there is no need for any command about Kahn’s if you haven’t checked it out, go back to the recent blog and read loud you’ll master it.

Question Decode:

• There is a directed graph with N nodes each node labeled from 0 to N -
• The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node I simple which means [ [1,2],[2,3],[5],[0],[5],[ ],[ ] ]
• node of 0 adjacent node 1 and 2 — — — — → 0 connected with 1 and 2
  node of 1 adjacent node 2 and 3 — — — — → 1 connected with 2 and 3
• A node is a terminal node (crucial phrase) if there are no outgoing edges
• A node is a safe node If every possible path starting from that node leads to a terminal node or another safe node
• returning all the safe nodes in ascending order

Let’s break through visually:

We’ve discovered how to find an in-degree (no incoming edges) and push it into the queue then extract the node from the queue but here, there are slight differences instead of incoming we need to find outgoing edges, terminal node, make them as a safe node don’t be afraid to see this phrase just wait.

1. Terminal Nodes (Safe Nodes): Nodes with no outgoing edges are termed terminal nodes. These nodes have reached a state where there are no further transitions, making them safe
2. Connected to Terminal Nodes: Any node that is directly or indirectly connected to a terminal node is also considered safe. This is because, if a node is part of a path that leads to a terminal node, it is in a state where no further transitions can occur.

the question states

You might ask what about 1, the 1 has two paths right If both paths from a node lead to the terminal it can be considered a safe node However in a case where one path leads to the terminal and the other leads back to the node itself the node cannot be considered safe so exact same as 3.

Approaching the problem and core strategies:

What do you think about which algorithm yes you’re correct Kahn’s algorithm but since we’ve learned only finding the indegree of the node as I told you before we need to find the out-degree of the node, ahh out-degree What do you mean marudhu but you said in Kahn’s can only find an in-degree of nodes but here we are going to do some small change with the graph.

• Initially reversing the edges of nodes which means out-degree to in-degree exactly startingly 0 pointing to 1 and 2 so 0 out-degree 2 but we can’t find with Kahn’s if we reverse the edges we have one option to find the in-degree of all nodes with Kahn’s isn’t so after reversing 1 and 2 pointing to 0 now 0 has 2 in-degree that’s what we are going to do here
• After reversing the edges, I hope you know what we do next with Kahn’s finds all the indegrees of all nodes so those who startingly have 0 indegrees then marked as terminal nodes, then reducing the in-degree their adjacent nodes become safe please keep continuing until no nodes have no in degree which means 0 in-degree finally extract all nodes from the queue presenting the list of safe nodes.

what’s all these phrases marudhu out-degree and reverse the edges find the indegree push into queue if seems like intimidated, don’t be afraid just see the below image you will understand what we explained above the statement.

Visual of Out-degree to In-degree:

Out-degree to in-degree with visual

How to reverse the Edges:

Yup! Great question bit challenging part as well don’t worry just use a simple for loop. Whatever node is at the current ith index, make it adjacent to the nodes at that ith index,
[ [1,2],[2,3],[5],[0],[5],[ ],[ ] ] — — — → [ [3],[0],[0,1],[1],[],[2,4], [ ] ]

// reverse edges 
    let reversedAdj = new Array(graph.length).fill(null).map(() => []);

    let indegree = new Array(graph.length).fill(0);
// example currently 0th index has 1 and 2 so make it adjacent of the nodes
// at the 0th index so just push the 0 into 1st and 2nd space of the array
// paralley getting the indegree of the node
// if you don't know how to find indegree just go back and read the Mastery kahn's blogs once
    for (let i = 0; i < graph.length; i++) {
      for (let adj of graph[i]) {
        reversedAdj[adj].push(i);
        indegree[i]++;
      } 
    }

Once you reverse all the edges, as I told you before then everything same as what we did at the Kahn’s just find those who have 0 indegrees and push them into the queue until no nodes have no in the degree which means 0 in-degree, finally showing the list to them.

Code Showcase:

class Solution {
  eventualStates(graph) {
// reverse edgess not adjlist
    let reversedAdj = new Array(graph.length).fill(null).map(() => []);

    let indegree = new Array(graph.length).fill(0);
    for (let i = 0; i < graph.length; i++) {
      for (let adj of graph[i]) {
        reversedAdj[adj].push(i);
        indegree[i]++;
      } 
    }
// after reversed edges just simple concept no chaos
    // console.log(reversedAdj, "reversed adj");
    // console.log(indegree);
    let safeNode = [];
    let queue = [];
    for (let i = 0; i < reversedAdj.length; i++) {
      if (indegree[i] === 0) {
        queue.push(i);
      }
    }
    // console.log(queue);
    while (queue.length !== 0) {
      let vertex = queue.shift();
      safeNode.push(vertex);

      for (let remove of reversedAdj[vertex]) {
        indegree[remove]--;
        if (indegree[remove] === 0) {
          queue.push(remove);
        }
      }
    }
    let out = safeNode.sort((a, b) => a - b);
    return out;
  }
}

let graph = [[1, 2], [2, 3], [5], [0], [5], [], []];

let data = new Solution();
let output = data.eventualStates(graph);
console.log("commited safe states", output);

Welcome to onboard of conclusion:

Thanks for staying with me so far, I am confident you all have learned some new techniques or something from our regular blog, take it one step at a time. Be kind to yourself, and always prioritize your learning. A big ‘thank you’ to each one of you! thanks a ton please hit the follow button and applaud the button below the blog you will immediately get a popup on your screen with new blog notifications.