ES242. Data Structures and Algorithms I. Week 08 Lab
ES242. Data Structures and Algorithms I.
Lab 08
Depth First Search
In this exercise your goal is to output a DFS traversal of a given graph G starting from a given source s.
Input Format
The first line of input is three space-separated integers n, m and s, denoting the number of vertices and edges of G, and the id of the source vertex, respectively. Vertices are indexed from 0 to n-1.
The next m lines of code are two space separated integers u and v in the range 0 and n-1, indicating an (undirected) edge between vertices u and v.
The last line is a pair of space-separated integers x and y.
Output Format
The output is a sequence of vertices in the order in which they were pushed on to the stack. Assume that you always find your lexicographically smallest unvisited neighbor in your DFS implementation.
Sample I/O
Sample Input
Sample Output
Recall that a path in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph (also known as a DAG) is a directed graph that has no cycles.
You are given a directed graph G. Your task is to determine whether the input graph is a DAG.
Note that the vertices are 0-indexed. That is, the vertices are numbered as 0 \ldots n-1.
Your code should output YES if G is a DAG, else NO
Input Format
The first line contains an integer n, the number of nodes in the graph.
The next line contains an integer m, denoting the number of edges in the graph.
The next m input lines contain two space-separated integers u,v denoting a directed edge from u to v (u->v).
Output Format
Output YES if G is a DAG, else NO
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
