I tried to solve the question using topological sort using BFS .
Here’s the code
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
int m = graph[0].length;
int V [][]= new int[n][m];
List<List<Integer>> adj=new ArrayList<>();
List<List<Integer>> adjRev = new ArrayList<>();
for(int i=0;i<n;i++){
for(int j=0;j<m;i++){
adjRev.add(new ArrayList<>());
}
}
int indeg[] = new int[n];
for(int i=0;i<n;i++){
for(int j=0;j<m;i++){
for(int it : adj.get(i)){
adjRev.get(it).add(i);
indeg[i]++;
}
}
}
Queue<Integer> q = new LinkedList<>();
List<Integer> safeNodes = new ArrayList<>();
for(int i=0;i<n ;i++){
for(int j=0;j<m;i++){
if(indeg[i]==0){
q.add(i);
}
}
}
while(!q.isEmpty()){
int node = q.peek();
q.remove();
safeNodes.add(node);
for(int it : adjRev.get(node)){
indeg[it]-- ;
if(indeg[it] == 0) q.add(it);
}
}
Collections.sort(safeNodes);
return safeNodes;
}
}
Earlier the code was facing index out of bound error .So I tried to fox it by taking a two dimensional Array named ‘V’ with ‘n’ number of rows and ‘m’ number of columns which had the count of adjacency matrix of the given graph.
New contributor
Kasturi Shirole is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.