BFS Cơ bản

Tác giả:

Dạng bài

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho một đồ thị vô hướng gồm $N$ đỉnh đánh số từ 1 tới $N$ và $M$ cạnh. Độ dài của mỗi cạnh có giá trị là 1. Một đồ thị sẽ có 1 nút trung tâm $S$.

Yêu cầu: với mỗi đỉnh có thể tới được từ đỉnh $S$, tính khoảng cách ngắn nhất từ đỉnh đó tới $S$ và in ra các đỉnh theo thứ tự khoảng cách ngắn nhất tăng dần. Lưu ý: nếu 2 đỉnh có khoảng cách bằng nhau thì nhãn nào nhỏ hơn sẽ đứng trước.

Input

Dòng đầu gồm 3 số nguyên $N, M, S$ ($N \leq 100000, M \leq 100000, 1 \leq S \leq N$)
M dòng sau mỗi dòng gồm 2 số thể hiện 2 đầu của một cạnh.

Output

In ra số dòng tương ứng với số đỉnh có thể tới được từ S theo thứ tự khoảng cách ngắn nhất tăng dần.
Trên mỗi dòng in ra nhãn của đỉnh đó và khoảng cách ngắn nhất của đỉnh đó tới S.

Example

Test 1

Input

Output

Bình luận

10
jumptozero 9:01 a.m. 30 Tháng 5, 2021
Mình xin trình bày lời giải bài này theo từng bước như sau:

Bước 1: Biểu diễn đồ thị đã cho dưới dạng danh sách đỉnh kề, cụ thể dưới hình sau:

Bước 2: Gọi $d[i]$ là khoảng cách ngắn nhất từ đỉnh $i$ đến đỉnh $s$ với mọi $i=1,2,...,n$ và giá trị của tất cả $d[i]$ này ban đầu là vô cùng (cụ thể ở đây ta gán $d[i]=inf$ với $inf=10^{18}$)

Công việc tiếp theo đó là chúng ta đi tính $d[i]$ thông qua hàm $BFS()$ như sau:

\[$ queue<ll> q; void bfs(ll source) { d[source] = 0; q.push(source); dau[source] = 1; while (!q.empty()) { ll p = q.front(); q.pop(); for (auto ke : edges[p]) { if (dau[ke] == 1) continue; d[ke] = min(d[ke], d[p] + 1); q.push(ke); dau[ke] = 1; } } } $\]

Mình xin giải thích cụ thể đoạn code trên như sau:

Step 1: Rõ ràng ta có ngay $d[s]=0$

Step 2: Tiếp theo những đỉnh mà kề với $s$ thì sẽ được tính theo công thức như sau: $d[v]=min(d[v],d[s]+1)$ (Với mọi $v$ kề với $s$).

Một điều quan trọng được xem như linh hồn của hàm BFS đó chính là cấu trúc dữ liệu queue (Bạn nào chưa biết có thể lên mạng tìm hiểu, vì nó là một cấu trúc dữ liệu kinh điển và được sử dụng thường xuyên), ở đây mình chỉ đề cập đến hai lệnh phổ biến hàm queue hai dùng đó là:

$q.pop()$: Lấy phần tử đầu tiên ra khỏi queue. Ví dụ ban đầu $q = \left\{4,3,6,7\right\}$. Thì sau khi thực hiện lệnh: $q.pop(), q = \left\{3,6,7\right\}$

$p=q.front()$: Gán phần tử đầu tiên của queue cho $p$. Vì dụ $q\left\{4,7,8\right\}$. Thì $p = q.front() = 4$

Step 3: Ta cần dùng một mảng để đánh dấu những đỉnh đã được duyệt qua, để tránh hàm while lặp vô tận.

Bước 3: Đó là bước in ra. Ở bước này, ta chú ý rằng, sau khi đã tính xong mảng $d[]$. Ta chỉ cần in ra những đỉnh nào mà có $d[i]\ne inf$. Nhưng trước đó ta cần xử lý một chút, để in ra đúng theo yêu cầu bài toán, đó là các đỉnh được in ra phải theo thứ tự tăng dần của $d[i]$ và nếu có hai đỉnh nào cùng $d[i]$ thì nhãn nào bé hơn sẽ in ra trước.

Do đó ta nên lưu những đỉnh có $d[i]\ne inf$ vào một vector và sau đó sort lại là xong:

Cụ thể:

\[$ vector<pair<ll, ll>> res; ... for (i = 0; i < n; i++) res.push_back({d[i], i}); // cout<<res.size()<<'\n'; sort(res.begin(), res.end()); for (auto p : res) { if (p.first == inf) continue; cout << p.second + 1 << " " << p.first << '\n'; } $\]

Như vậy là bài toán đã được giải quyết xong !

Ps:

Nếu có gì thắc mắc hoặc sai sót các bạn cứ tự nhiên comment nhé

Các bạn có thể tham khảo code tại đây