# [Solved] ADA Mini Homework 2

Click And Check all our Assignments

10 USD \$

Category: Tag:

# To DFS, or to BFS, that is the question

## Problem Description

TL; DR: Given a connected graph with N vertices and M bidirectional edges, please output the lexicographically smallest DFS sequence and the lexicographically smallest BFS sequence.

BB Travel Inc., a traveling agency in the ADA Kingdom, would like to launch a tourist plan that visit every city in the kingdom. The ADA Kingdom consists of N cities number from 1 to N, where the city numbered 1 is the capital. There are also M bidirectional road connecting pairs of cities. You can reach any city from any city using some of the roads.

The tourist plan should be a valid Depth-First Search (DFS) or Breadth-First Search (BFS) sequence of the kingdom starting from the capital (city 1). Thus, it should be a sequence of cities s1,s2,…,sN, where s1 = 1, and each city occurs exactly once. Additionally, to attract more customers, the plan should be as attractive as possible. We say plan s is more attractive than plan s, if s is lexicographically smaller than s.

Since BB Travel Inc. doesn’t know whether their customers prefer BFS order or DFS order yet, they ask you to help them find out the plan for both scenarios (i.e. one plan for DFS, and one plan for BFS).

## Glossary

Please see the course slides for the definition of Depth-First Search and Breadth-First Search. Note that for the case of BFS, the order is valid as long as we choose an unvisited vertex closest to the starting vertex every time.

A valid DFS/BFS sequence is a sequence s, such that there exists a DFS/BFS search order, where si is the i-th vertex added into the DFS/BFS tree.

A sequence s is lexicographically smaller than sif there exists a index t, such that and st < st.

## Input

The first line of the input contains two integers N and M, denoting the number of cities and the number of roads in the ADA Kingdom.

The next M lines describes the roads connecting the cities. The i-th line contains two integers ui and vi, denoting a bidirectional road connecting city ui and vi.

• 1 ≤ N ≤ 105
• 1 ≤ M ≤ 2 × 105
• 1 ≤ ui,vi N,∀1 ≤ i M
• ui ̸= vi,∀1 ≤ i M
• You can reach any city from any city using some of the roads.
• Every pair of cities is directly connected by at most one edge.

Test Group 0 (0 %)

• Sample Input

Test Group 2 (75 %)

Test Group 1 (25 %)

• N ≤ 1000
• M ≤ 2000

Please output two lines. The first line contains the most attractive DFS trip plan starting from the capital. The second line contains the most attractive BFS trip plan starting from the capital.

Sample Input 1 Sample Input 2

5 7

5 4

5 4

1 2

3 5

• 4
• 3
• 3
• 1
• 5

1 4

• 4
• 2

Sample Output 1

Sample Output 2

1 2 5 4 3 1 4 2 3 5

1 2 4 3 5 1 4 5 2 3

## Hint

1. bidirectional = undirected ̸= unidirectional
2. Make sure you understand the sample input/outputs before coding.
3. STL is your good firend. For example:
• You can use std::vector to store the graph (adjacency list).
• You can use std::sort to sort an array/vector/etc.

## Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Shopping Cart