Depth-First Search

View as PDF

Submit solution

Points: 100
Time limit: 1.5s
Memory limit: 977M

Author:
Problem type

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 v and e as space-separated integers. v represents the number of vertices in the graph, labelled from 0 to v-1, and e represents the number of edges in the graph.

Your next line will contain s, the source vertex to start the DFS from.

Your next e lines will contain 2 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:

  • 2 \le v \le 10^3
  • 0 \le s \le v-1
  • 1 \le e \le 10^6

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

There are no comments at the moment.