Directed Acyclic Graphs Given a directed graph as an adjacency list, you need to determine whether it is acyclic or not. Input Format Each of the lines in the input contains two space-separated integers, s and d, that represents an edge from the node s to d. Constraints Node numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1. Output Format The 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 0 0 1 0 2 0 3 1 2 1 3 2 3 2 4 4 5 5 6 Sample Output 0 1 Explanation 0 The example graph in this example is *Since there is no cycle in the graph, the result is 1
Directed Acyclic Graphs Given a directed graph as an adjacency list, you need to determine whether it is acyclic or not. Input Format Each of the lines in the input contains two space-separated integers, s and d, that represents an edge from the node s to d. Constraints Node numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1. Output Format The 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 0 0 1 0 2 0 3 1 2 1 3 2 3 2 4 4 5 5 6 Sample Output 0 1 Explanation 0 The example graph in this example is *Since there is no cycle in the graph, the result is 1
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Directed Acyclic Graphs
Given a directed graph as an adjacency list, you need to determine whether it is acyclic or not.
Input Format
- Each of the lines in the input contains two space-separated integers, s and d, that represents an edge from the node s to d.
Constraints
Node numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1.
Output Format
The 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 0
0 1 0 2 0 3 1 2 1 3 2 3 2 4 4 5 5 6
Sample Output 0
1
Explanation 0
The example graph in this example is
*Since there is no cycle in the graph, the result is 1
Transcribed Image Text:2
(5
3.
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.*;
2
10
11 vpublic class Solution {
12
13
public static class DirectedGraph {
14
/* Adjacency List representation of the given graph */
private Map<Integer, List<Integer>> adjList = new HashMap<Integer, List<Integer>> ();
15
16
public String tostring () {
StringBuffer s = new StringBuffer ();
for (Integer v : adjlist.keySet ())
s. append ("\n
return s.toString ();
17
18
19
20
" + v +" -> " + adjlist.get (v));
21
22
}
23
24
public void add (Integer vertex) {
if (adjList.containskey (vertex))
25
26
return;
27
adjlist.put(vertex, new ArrayList<Integer>());
28
29
30
public void add (Integer source, Integer dest) {
add (source);
add (dest);
adjlist.get (source).add (dest);
31
32
33
34
35
36
/* Indegree of each vertex as a Map<vertex, IndegreeValue> */
public Map<Integer, Integer> inDegree() {
Map<Integer, Integer> result = new HashMap<Integer, Integer> ();
for (Integer v : adjlist.keySet ())
result.put (v, ®);
for (Integer from : adjList.keySet ()) {
for (Integer to : adjlist.get(from)) {
37 -
38
39
40
41
42
43
result.put(to, result.get(to) + 1);
44
45
46
return result;
47
48
public Map<Integer, Integer> outDegree () {
Map<Integer, Integer> result = new HashMap<Integer, Integer> ();
for (Integer v: adjlist.keySet ()) result. put (v, adjList.get(v).size());
return result;
}
49
50
51
52
53
54
55
6,
4-
![48
public Map<Integer, Integer> outDegree () {
Map<Integer, Integer> result = new HashMap<Integer,Integer> ();
for (Integer v: adjList.keySet ()) result. put (v, adjlist.get (v).size());
return result;
49
50
51
'וכ
52
53
יככ
54
55
}
56
// Complete the isDAG function below.
public static boolean isDag (DirectedGraph digraph) {
י/כ
57
58
59
60
61
62
63
public static void main(String[] args) throws IOException {
64
65
BufferedWriter bufferredWriter = new BufferedWriter (new FileWriter (System.getenv ("OUTPUT PATH")));
66
67
BufferedReader bufferredReader = new BufferedReader (new InputStreamReader (System.in));
68
69
DirectedGraph digraph = new DirectedGraph ();
70
String line;
while ((line = bufferredReader.readLine ()) != nul1) {
String[] v = line.split(" ");
digraph.add (Integer.parseInt (v[0]), Integer.parseInt (v[1]));
71
72
12
73
74
75
76
77
bufferredwriter.write ((isDag(digraph) ? "1" : "0"));
78
bufferredReader.close ();
bufferredwriter.close ();
79
80
81
}
82 }
83](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F8bf221b6-1639-48b5-921c-5559c65156e9%2Fad2d9195-252f-4ac8-9b99-3eeca76e5681%2Fepratckf_processed.png&w=3840&q=75)
Transcribed Image Text:48
public Map<Integer, Integer> outDegree () {
Map<Integer, Integer> result = new HashMap<Integer,Integer> ();
for (Integer v: adjList.keySet ()) result. put (v, adjlist.get (v).size());
return result;
49
50
51
'וכ
52
53
יככ
54
55
}
56
// Complete the isDAG function below.
public static boolean isDag (DirectedGraph digraph) {
י/כ
57
58
59
60
61
62
63
public static void main(String[] args) throws IOException {
64
65
BufferedWriter bufferredWriter = new BufferedWriter (new FileWriter (System.getenv ("OUTPUT PATH")));
66
67
BufferedReader bufferredReader = new BufferedReader (new InputStreamReader (System.in));
68
69
DirectedGraph digraph = new DirectedGraph ();
70
String line;
while ((line = bufferredReader.readLine ()) != nul1) {
String[] v = line.split(" ");
digraph.add (Integer.parseInt (v[0]), Integer.parseInt (v[1]));
71
72
12
73
74
75
76
77
bufferredwriter.write ((isDag(digraph) ? "1" : "0"));
78
bufferredReader.close ();
bufferredwriter.close ();
79
80
81
}
82 }
83
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY