Module: Tìm kiếm theo chiều sâu. DFS


Problem

1/12

DFS: Bắt đầu (C++)

Theory Click to read/hide

DFS DFS
Tìm kiếm theo chiều sâu (DFS) là một trong những thuật toán chính trên biểu đồ. Thuật toán chạy trong O(N + M).
 
Thuật toán
Để bắt đầu, chúng tôi bắt đầu từ trên cùng, xem xét các phần tử con của phần trên cùng này và nếu chúng tôi chưa bao giờ nhập chúng, thì chúng tôi bắt đầu DFS từ chúng.


Problem

Viết thủ tục void dfs (int v) duyệt theo độ sâu của đồ thị vô hướng từ đỉnh bắt đầu S và xuất tất cả các đỉnh theo thứ tự duyệt, bắt đầu từ đỉnh S được phân tách bằng dấu cách trên một dòng.

Dòng đầu tiên chứa ba số N  - số đỉnh của đồ thị, M - số cạnh, S - điểm bắt đầu đỉnh. Trong các dòng M sau, 2 biến Ui và Vi được cung cấp , mô tả các cạnh của đồ thị. Tất cả các số trong đầu vào không vượt quá 1000.

Xuất tất cả các đỉnh theo thứ tự đi qua của DFS.

Trong chương trình trên, g[i][j] có nghĩa là có một cạnh giữa các đỉnh i và j, và trong mảng used chúng tôi đánh dấu xem chúng tôi đã đến đỉnh này chưa. 

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <vector>

using namespace std;

vector < vector < int > > g;
vector < bool > used;

void dfs(int v) 
{            
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, s, u, v;

	cin >> n >> m >> s;

	g.resize(n);
	used.resize(n);

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		g[u - 1].push_back(v - 1);
		g[v - 1].push_back(u - 1);
	}

	dfs(s - 1);
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!