Module: BFS - Đi bộ theo chiều rộng


Problem

1/6

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

Theory Click to read/hide

Tìm kiếm theo chiều rộng trước (BFS)
BFS (tìm kiếm theo chiều rộng, tìm kiếm theo chiều rộng) - một phương pháp duyệt đồ thị, rất thường được sử dụng trong cả thuật toán đơn giản và nâng cao. Tìm kiếm theo chiều rộng hoạt động bằng cách đi qua các cấp độ riêng lẻ của biểu đồ, bắt đầu từ nút nguồn và dần dần di chuyển ra khỏi nút đó. Điều này được thể hiện rõ ràng trong hình ảnh động.
Để viết BFS  đơn giản nhất, bạn cần có khả năng làm việc với cấu trúc dữ liệu cho phép bạn lấy từ đầu và đưa nó vào cuối, đồng thời có thể lưu trữ biểu đồ ở dạng danh sách kề (nghĩa là có hàng đợi).
 
Mô tả chính thức của thuật toán
1) Đặt số đỉnh bắt đầu tìm kiếm vào hàng đợi trống ban đầu.
2) Trích xuất đỉnh U từ đầu hàng đợi và đánh dấu nó là được sử dụng trong một mảng riêng.
3) Ở cuối hàng đợi, hãy thêm tất cả các đỉnh mà chúng ta có thể với tới bằng cách sử dụng cạnh từ đỉnh U, và các đỉnh chưa được gắn nhãn.
4) Nếu hàng đợi trống thì tất cả các nút của biểu đồ liên thông đã được quét, nếu không thì quay lại bước 2.
 
Độ phức tạp
Vì thuật toán truy cập tất cả các nút của biểu đồ trong trường hợp xấu nhất nên khi lưu trữ biểu đồ dưới dạng danh sách kề, độ phức tạp về thời gian của thuật toán là O(|V| + |E|) , trong đó V là tập hợp các đỉnh của đồ thị và E là tập hợp các cạnh. Nói cách khác, thuật toán hoạt động trong trường hợp xấu nhất đối với số số cạnh + số đỉnh.

 

Problem

Một số làng được nối với nhau bằng các con đường, có thể được biểu diễn dưới dạng đồ thị vô hướng. Các đỉnh của biểu đồ này là các làng và các cạnh là các con đường giữa các làng (biểu đồ có thể chứa các chu trình). Được biết, trong làng S một artel Những người bán rong. Mỗi buổi sáng, để bán những món đồ lặt vặt nhỏ của họ, những người bán rong đi đến những ngôi làng chưa đến thăm và từ đó có một con đường từ ngôi làng hiện tại. Nhóm người bán rong luôn được chia thành từng nhóm để có thể đi khắp các làng có đường từ làng hiện nay đi trong một ngày.
Trong bao nhiêu ngày những người bán hàng rong sẽ đến tất cả các ngôi làng? Viết hàm BFS sẽ trả về câu trả lời cho tác vụ.

 
Đầu vào
Dòng đầu tiên chứa 3 số nguyên n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - số làng, số đường giữa chúng và số làng nơi nhóm người bán rong đóng trụ sở.  ;Trong các dòng m sau mỗi dòng chứa 2 số u, v(\(1 < = u, v <= n\ )) - số của hai làng giữa hai làng có một con đường. Các làng được lập chỉ mục với 1.

Dấu ấn
In ra một số - những người bán rong sẽ mất bao nhiêu ngày để đi hết các ngôi làng.

 

Ví dụ
<đầu>

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++
# Đầu vào Đầu ra
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4
Write the program below 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>

using namespace std;

vector<bool> used;   
// used[i] = true, если мы были в вершине i
vector<vector<int> > g;   // список смежности
vector<int> tm;     
// tm[i] - день, когда в деревню i 
// пришла артель коробейников
int n, m, s;

int bfs()
{                   
}

int main()
{
	cin >> n >> m >> s;
	s--;
	g.resize(n);
	tm.resize(n);
	used.assign(n, false);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout << bfs();
	return 0;
}

     

Program check result

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