Problem Statement
Implement depth-first search in an undirected graph.
During the traversal, always select the smallest unvisited vertex as the next one.
Input
Your first line will contain and as space-separated integers. represents the number of vertices in the graph, labelled from to , and represents the number of edges in the graph.
Your next line will contain , the source vertex to start the DFS from.
Your next lines will contain space-separated numbers, specifying that there is an edge between the two specified vertices.
Output
The DFS traversal, separated by line breaks.
Constraints
For all test cases:
Example 1
Input
7 6
0
0 1
0 2
1 3
1 4
2 5
2 6
Output
0
1
3
4
2
5
6
Python Template
v, e = map(int, input().split())
s = input()
edges = [tuple(map(int, input().split(" "))) for _ in range(e)]
# print(...)
Recursive Limit
Python has this thing called a recursion limit which is pretty bad. If you want to bypass it, put the following magic words at the start of your file...
import sys
sys.setrecursionlimit(1000000)
Comments