Editorial for DFS cơ bản

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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é !


Comments

There are no comments at the moment.