Commit8e7e64d

committed

Added Find Eventual Safe States.java

1 parentb86b448 commit8e7e64dCopy full SHA for 8e7e64d

File tree

+35

-0

lines changed

+35

-0

lines changed

Lines changed: 35 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,35 @@`
	`1`	`+classSolution {`
	`2`	`+publicList<Integer>eventualSafeNodes(int[][]graph) {`
	`3`	`+intn =graph.length;`
	`4`	`+Map<Integer,Set<Integer>>map =newHashMap<>();`
	`5`	`+int[]indegree =newint[n];`
	`6`	`+for (inti =0;i <n;i++) {`
	`7`	`+for (Integerconn :graph[i]) {`
	`8`	`+indegree[i]++;`
	`9`	`+map.computeIfAbsent(conn,k ->newHashSet<>()).add(i);`
	`10`	`+ }`
	`11`	`+ }`
	`12`	`+Queue<Integer>queue =newLinkedList<>();`
	`13`	`+for (inti =0;i <n;i++) {`
	`14`	`+if (indegree[i] ==0) {`
	`15`	`+queue.add(i);`
	`16`	`+ }`
	`17`	`+ }`
	`18`	`+List<Integer>result =newArrayList<>();`
	`19`	`+while (!queue.isEmpty()) {`
	`20`	`+intsize =queue.size();`
	`21`	`+while (size-- >0) {`
	`22`	`+intremoved =queue.remove();`
	`23`	`+result.add(removed);`
	`24`	`+for (Integerconn :map.getOrDefault(removed,newHashSet<>())) {`
	`25`	`+indegree[conn]--;`
	`26`	`+if (indegree[conn] ==0) {`
	`27`	`+queue.add(conn);`
	`28`	`+ }`
	`29`	`+ }`
	`30`	`+ }`
	`31`	`+ }`
	`32`	`+Collections.sort(result);`
	`33`	`+returnresult;`
	`34`	`+ }`
	`35`	`+}`

Comments

(0)