Hướng dẫn cho DFS cơ bản

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: jumptozero

Mình xin chia sẻ lời giải bài này như sau:

Bước 1: Đọc dữ liệu và đưa về danh sách đỉnh kề tương tự bài BFS Cơ bản

Bước 2: Ta sẽ duyệt qua tất cả các đỉnh của đồ thị và kiểm tra rằng, đỉnh $i$ nào đó đã thuộc về một đồ thị liên thông nào chưa ? Nếu chưa thì ta sử dụng hàm DFS để gôm tất cả những đỉnh có thể đến $i$ về thành một đồ thị liên thông ! Và ở đây ta sử dụng một biến $dem$ để đếm số lượng thành phần liên thông .

Và ở đây mình sử dụng mảng $dau[]$ để đánh dấu đỉnh $i$ đã thuộc về một đồ thị liên thông nào chưa ?

Ban đầu, tất cả các phần tử của mảng $dau[]$ đều bằng $0$

Cụ thể các bạn có thể xem hình ảnh dưới đây:

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

Bước 3: ** Triển khai hàm $DFS()$. Về bản chất hàm $DFS$ tương tự hàm $BFS$ nhưng chỉ khác cấu trúc dữ liệu đó là ở $BFS$ ta sử dụng **queue thì ở $DFS$ ta sử dụng stack. Ở đây, mình sẽ chia sẻ $2$ lệnh cơ bản của stack đó là :

$p=st.top()$: Có nghĩa là lấy phần tử trên cùng của stack
$st.pop()$: Loại bỏ phần tử trên cùng của stack

Để dễ hình dung, các bạn có thể xem ảnh ở dưới đây !

\[$ void dfs(ll source) { dau[source] = 1; stack<ll> st; st.push(source); while (!st.empty()) { ll p = st.top(); st.pop(); for (auto v : edges[p]) { if (dau[v] == 1) continue; dau[v] = 1; st.push(v); } } } $\]

Ps:

Ở đây, chúng ta có thể sử dụng BFS thay cho DFS
Các bạn có thể tham khảo code mình tại đây
Nếu có gì khó hiểu, các bạn comment nhé !

Bình luận

Không có bình luận nào.