Directed Acyclic GraphsGiven a directed graph as an adjacency list, you need to determine whether it is acyclic or not.Input FormatEach of the lines in the input contains two space-separated integers, s and d, that represents an edge from the node s to d.ConstraintsNode numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1.Output FormatThe output of the program is 0 or 1, depending on the result of the isDag() function. If it returns TRUE, output is 1, otherwise it is 0.Sample Input 00 1 0 2 0 3 1 2 1 3 2 3 2 4 4 5 5 6Sample Output 01Explanation 0The example graph in this example is*Since there is no cycle in the graph, the result is 1 2(53.1 vimport java.io.*;import java.math.*;3 import java.security.*;4 import java.text.*;5 import java.util.*;6 import java.util.concurrent.*;import java.util.function.*;8 import java.util.regex. *;9 import java.util.stream.*;21011 vpublic class Solution {1213public static class DirectedGraph {14/* Adjacency List representation of the given graph */private Map adjList = new HashMap ();1516public String tostring () {StringBuffer s = new StringBuffer ();for (Integer v : adjlist.keySet ())s. append ("
return s.toString ();17181920" + v +" - " + adjlist.get (v));2122}2324public void add (Integer vertex) {if (adjList.containskey (vertex))2526return;27adjlist.put(vertex, new ArrayList());282930public void add (Integer source, Integer dest) {add (source);add (dest);adjlist.get (source).add (dest);313233343536/* Indegree of each vertex as a Map */public Map inDegree() {Map result = new HashMap ();for (Integer v : adjlist.keySet ())result.put (v, ®);for (Integer from : adjList.keySet ()) {for (Integer to : adjlist.get(from)) {37 -383940414243result.put(to, result.get(to) + 1);444546return result;4748public Map outDegree () {Map result = new HashMap ();for (Integer v: adjlist.keySet ()) result. put (v, adjList.get(v).size());return result;}495051525354556,4- 48public Map outDegree () {Map result = new HashMap ();for (Integer v: adjList.keySet ()) result. put (v, adjlist.get (v).size());return result;495051'וכ5253יככ5455}56// Complete the isDAG function below.public static boolean isDag (DirectedGraph digraph) {י/כ57585960616263public static void main(String[] args) throws IOException {6465BufferedWriter bufferredWriter = new BufferedWriter (new FileWriter (System.getenv ("OUTPUT PATH")));6667BufferedReader bufferredReader = new BufferedReader (new InputStreamReader (System.in));6869DirectedGraph digraph = new DirectedGraph ();70String line;while ((line = bufferredReader.readLine ()) != nul1) {String[] v = line.split(" ");digraph.add (Integer.parseInt (v[0]), Integer.parseInt (v[1]));7172127374757677bufferredwriter.write ((isDag(digraph) ? "1" : "0"));78bufferredReader.close ();bufferredwriter.close ();798081}82 }83

Question

Directed Acyclic GraphsGiven a directed graph as an adjacency list, you need to determine whether it is acyclic or not.Input FormatEach of the lines in the input contains two space-separated integers, s and d, that represents an edge from the node s to d.ConstraintsNode numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1.Output FormatThe output of the program is 0 or 1, depending on the result of the isDag() function. If it returns TRUE, output is 1, otherwise it is 0.Sample Input 00 1 0 2 0 3 1 2 1 3 2 3 2 4 4 5 5 6Sample Output 01Explanation 0The example graph in this example is*Since there is no cycle in the graph, the result is 1 2(53.1 vimport java.io.*;import java.math.*;3 import java.security.*;4 import java.text.*;5 import java.util.*;6 import java.util.concurrent.*;import java.util.function.*;8 import java.util.regex. *;9 import java.util.stream.*;21011 vpublic class Solution {1213public static class DirectedGraph {14/* Adjacency List representation of the given graph */private Map> adjList = new HashMap> ();1516public String tostring () {StringBuffer s = new StringBuffer ();for (Integer v : adjlist.keySet ())s. append (&#34;
return s.toString ();17181920&#34; + v +&#34; -> &#34; + adjlist.get (v));2122}2324public void add (Integer vertex) {if (adjList.containskey (vertex))2526return;27adjlist.put(vertex, new ArrayList());282930public void add (Integer source, Integer dest) {add (source);add (dest);adjlist.get (source).add (dest);313233343536/* Indegree of each vertex as a Map */public Map inDegree() {Map result = new HashMap ();for (Integer v : adjlist.keySet ())result.put (v, ®);for (Integer from : adjList.keySet ()) {for (Integer to : adjlist.get(from)) {37 -383940414243result.put(to, result.get(to) + 1);444546return result;4748public Map outDegree () {Map result = new HashMap ();for (Integer v: adjlist.keySet ()) result. put (v, adjList.get(v).size());return result;}495051525354556,4- 48public Map outDegree () {Map result = new HashMap ();for (Integer v: adjList.keySet ()) result. put (v, adjlist.get (v).size());return result;495051'וכ5253יככ5455}56// Complete the isDAG function below.public static boolean isDag (DirectedGraph digraph) {י/כ57585960616263public static void main(String[] args) throws IOException {6465BufferedWriter bufferredWriter = new BufferedWriter (new FileWriter (System.getenv (&#34;OUTPUT PATH&#34;)));6667BufferedReader bufferredReader = new BufferedReader (new InputStreamReader (System.in));6869DirectedGraph digraph = new DirectedGraph ();70String line;while ((line = bufferredReader.readLine ()) != nul1) {String[] v = line.split(&#34; &#34;);digraph.add (Integer.parseInt (v[0]), Integer.parseInt (v[1]));7172127374757677bufferredwriter.write ((isDag(digraph) ? &#34;1&#34; : &#34;0&#34;));78bufferredReader.close ();bufferredwriter.close ();798081}82 }83

Accepted Answer

public static boolean isDAG(int z, boolean [] visited, boolean [] recursionStack){…