2. Write a C++ program called hw6_2.cpp that implements the Depth-First Search (DFS) algorithmusing a stack and a mark array as you learned in the class.

Input format: This is a sample input from a user.

3

2

0 1

1 2

The first line (= 3 in the example) indicates that there are three vertices in the graph. For the homework, you can assume that the first vertex starts from the number 0. The second line (= 2 in the example) represents the number of edges, and following two lines are the edge information. This is the graph with the input information.

Sample Run 0: Assume that the user typed the following lines

3

2

0 1

1 2

This is the correct output. Your program should display the mark array of DFS. For the problem, you can assume that the starting vertex is always 0. And also, you can assume that the graph is connected.

Mark[0]:1

Mark[1]:2

Mark[2]:3

Sample Run 1: Assume that the user typed the following lines

5

6

0 1

0 2

0 3

1 3

2 3

3 4

This is the correct output.

Mark[0]:1

Mark[1]:2

Mark[2]:5

Mark[3]:3

Mark[4]:4

Sample Run 2: Assume that the user typed the following lines

5

6

0 1

0 2

0 3

1 4

2 3

3 4

This is the correct output.

Mark[0]:1

Mark[1]:2

Mark[2]:4

Mark[3]:5

Mark[4]:3

[Hint] In the lecture, we used a stack for the operation of DFS algorithm. So, you can use an explicit stack to implement it. However, you can use a recursive function which uses an implicit stack. The following is the pseudocode with a recursive function and it may make your implementation easier.

// This is the main function named DFS().

// This is the recursive function named dfs().

// Dont be confused with the main function DFS().