Bài 18.2: Thuật toán DFS và ứng dụng

Trong thế giới rộng lớn của Cấu trúc dữ liệu và Giải thuật, đồ thị (graph) là một trong những cấu trúc mạnh mẽ và linh hoạt nhất. Chúng ta sử dụng đồ thị để mô hình hóa mọi thứ từ mạng xã hội, bản đồ đường đi, đến các hệ thống phụ thuộc giữa các tác vụ. Để có thể hiểu, phân tích, và giải quyết các bài toán trên đồ thị, chúng ta cần những công cụ để "thám hiểm" hoặc "duyệt" qua các đỉnh và cạnh của chúng. Một trong những công cụ mạnh mẽ và cực kỳ quan trọng chính là Thuật toán Duyệt theo chiều sâu (Depth-First Search - DFS).

DFS là một trong hai thuật toán duyệt đồ thị cơ bản nhất (cùng với Duyệt theo chiều rộng - BFS). Như tên gọi của nó, DFS có cách tiếp cận khác biệt: nó cố gắng đi "sâu" nhất có thể vào một nhánh của đồ thị trước khi quay trở lại và khám phá các nhánh khác. Hãy cùng "lặn sâu" (pun intended!) vào cách DFS hoạt động và những ứng dụng thú vị của nó.

DFS Hoạt Động Như Thế Nào?

Hãy tưởng tượng bạn đang ở trong một mê cung rộng lớn và muốn tìm đường. Chiến lược của DFS giống như việc bạn chọn một lối đi, đi theo nó đến tận cùng cho đến khi gặp ngõ cụt hoặc nơi đã đi qua. Nếu gặp ngõ cụt, bạn quay ngược lại (backtrack) đến điểm giao nhau gần nhất mà bạn chưa khám phá hết các lối đi khác, và chọn một lối đi mới chưa được thử. Quá trình này lặp lại cho đến khi bạn đã khám phá mọi nơi có thể từ điểm bắt đầu.

Về mặt kỹ thuật, DFS hoạt động dựa trên nguyên lý của ngăn xếp (stack). Khi đến một đỉnh, thuật toán sẽ:

Đánh dấu đỉnh đó là đã được thăm (visited).
"Thăm" đỉnh đó (ví dụ: in ra tên đỉnh).
Duyệt qua tất cả các đỉnh kề (neighbors) của đỉnh hiện tại.
Đối với mỗi đỉnh kề chưa được thăm:
- Gọi đệ quy (hoặc đẩy vào ngăn xếp) thuật toán DFS cho đỉnh kề đó. Quá trình này tiếp tục đệ quy, đưa thuật toán đi sâu vào đồ thị.

Cơ chế đệ quy tạo ra hành vi giống như ngăn xếp: các lời gọi hàm được xếp chồng lên nhau. Khi một lời gọi đệ quy kết thúc (vì đỉnh đó không còn đỉnh kề chưa thăm), thuật toán quay trở lại lời gọi trước đó trên ngăn xếp, tức là quay trở lại đỉnh "nông" hơn để tiếp tục khám phá các nhánh khác.

Các Bước Của Thuật Toán DFS

Một cách hình thức hơn, các bước của DFS cho một đồ thị $G = (V, E)$ và một đỉnh bắt đầu $s \in V$ có thể được mô tả như sau:

Khởi tạo một tập hợp (hoặc mảng boolean) visited để lưu trữ các đỉnh đã được thăm. Ban đầu, không có đỉnh nào được thăm.
Bắt đầu DFS từ đỉnh $s$.
Hàm DFS(u):
- Đánh dấu đỉnh u là đã thăm: visited[u] = true.
- Thực hiện các thao tác cần thiết trên đỉnh u (ví dụ: in u).
- Với mỗi đỉnh v kề với u (tức là có cạnh (u, v) trong đồ thị):
  - Nếu v chưa được thăm (visited[v] là false):
    - Gọi đệ quy DFS(v).

Nếu đồ thị có thể không liên thông (disconnected), bạn cần lặp qua tất cả các đỉnh trong đồ thị. Nếu gặp một đỉnh chưa được thăm, bắt đầu một quá trình DFS mới từ đỉnh đó. Mỗi lần bắt đầu một quá trình DFS mới từ một đỉnh chưa thăm sẽ khám phá ra một thành phần liên thông (connected component) mới của đồ thị.

Triển Khai DFS Bằng C++

Để triển khai DFS, chúng ta cần biểu diễn đồ thị. Biểu diễn phổ biến và hiệu quả nhất cho các thuật toán duyệt đồ thị thường là danh sách kề (adjacency list). Với danh sách kề, chúng ta sử dụng một mảng hoặc vector, trong đó mỗi phần tử i chứa một danh sách (ví dụ: std::vector hoặc std::list) các đỉnh kề với đỉnh i.

Hãy xem một ví dụ triển khai DFS cơ bản để duyệt qua tất cả các đỉnh có thể tới được từ một đỉnh bắt đầu.

#include <iostream>
#include <vector>
#include <list> // Có thể dùng vector<vector<int>> thay cho vector<list<int>>

// Sử dụng vector của vector cho danh sách kề
// adj[i] sẽ là một vector chứa các đỉnh kề với đỉnh i
std::vector<std::vector<int>> adj;

// Mảng boolean để theo dõi các đỉnh đã được thăm hay chưa
std::vector<bool> visited;

// Hàm DFS đệ quy
void dfs(int u) {
    // 1. Đánh dấu đỉnh hiện tại u là đã thăm
    visited[u] = true;

    // 2. "Thăm" đỉnh hiện tại (ví dụ: in ra)
    std::cout << u << " ";

    // 3. Duyệt qua tất cả các đỉnh kề với u
    // Trong danh sách kề, adj[u] chứa các đỉnh kề với u
    for (int v : adj[u]) {
        // 4. Nếu đỉnh kề v chưa được thăm
        if (!visited[v]) {
            // Gọi đệ quy hàm dfs cho đỉnh v
            dfs(v);
        }
    }
}

int main() {
    // Giả sử đồ thị có 5 đỉnh (0, 1, 2, 3, 4)
    int numVertices = 5;
    adj.resize(numVertices); // Cấp phát không gian cho numVertices danh sách kề
    visited.resize(numVertices, false); // Khởi tạo tất cả đỉnh là chưa thăm

    // Thêm các cạnh vào đồ thị
    // Đồ thị ví dụ:
    // 0 -- 1
    // |    |
    // 2 -- 3
    //  \  /
    //   4

    // Đỉnh 0 kề với 1 và 2
    adj[0].push_back(1);
    adj[0].push_back(2);

    // Đỉnh 1 kề với 0 và 3
    adj[1].push_back(0); // Vì là đồ thị vô hướng, thêm cạnh ngược lại
    adj[1].push_back(3);

    // Đỉnh 2 kề với 0, 3 và 4
    adj[2].push_back(0);
    adj[2].push_back(3);
    adj[2].push_back(4);

    // Đỉnh 3 kề với 1, 2 và 4
    adj[3].push_back(1);
    adj[3].push_back(2);
    adj[3].push_back(4);

    // Đỉnh 4 kề với 2 và 3
    adj[4].push_back(2);
    adj[4].push_back(3);

    std::cout << "Duyet DFS bat dau tu dinh 0: ";
    // Bắt đầu quá trình DFS từ đỉnh 0
    dfs(0); 
    std::cout << std::endl; // In ra một dòng mới sau khi hoàn thành duyệt

    // Lưu ý: Nếu đồ thị không liên thông, cần một vòng lặp trong main
    // để đảm bảo tất cả các thành phần liên thông đều được thăm.
    // Ví dụ:
    /*
    std::fill(visited.begin(), visited.end(), false); // Reset visited
    int component_count = 0;
    for(int i = 0; i < numVertices; ++i) {
        if (!visited[i]) {
            std::cout << "Duyet thanh phan lien thong moi bat dau tu dinh " << i << ": ";
            dfs(i);
            component_count++;
            std::cout << std::endl;
        }
    }
    std::cout << "So luong thanh phan lien thong: " << component_count << std::endl;
    */


    return 0;
}

Giải thích Code:

Chúng ta sử dụng std::vector<std::vector<int>> adj; để lưu trữ danh sách kề. adj[i] là một vector lưu trữ các đỉnh mà đỉnh i có cạnh nối tới.
std::vector<bool> visited; là một vector boolean, kích thước bằng số đỉnh. visited[i] là true nếu đỉnh i đã được thăm trong quá trình DFS hiện tại, và false ngược lại.
Hàm dfs(int u) là trái tim của thuật toán đệ quy:
- Nó đánh dấu đỉnh u là đã thăm ngay khi vào hàm.
- Sau đó, nó in ra đỉnh u (đây là bước "thăm").
- Vòng lặp for (int v : adj[u]) duyệt qua tất cả các đỉnh v mà u có cạnh nối tới.
- Điều kiện if (!visited[v]) là cực kỳ quan trọng để tránh vòng lặp vô hạn trong đồ thị có chu trình và đảm bảo mỗi đỉnh chỉ được xử lý một lần.
- Nếu v chưa thăm, chúng ta gọi dfs(v) - đây chính là bước đệ quy đi sâu xuống.
Trong main, chúng ta khởi tạo đồ thị với 5 đỉnh và thêm các cạnh. Sau đó, gọi dfs(0) để bắt đầu duyệt từ đỉnh 0. Toàn bộ thành phần liên thông chứa đỉnh 0 sẽ được duyệt.

Phân tích Độ phức tạp

Độ phức tạp thời gian: DFS thăm mỗi đỉnh và mỗi cạnh một lần duy nhất. Với biểu diễn danh sách kề, việc duyệt qua các đỉnh kề của một đỉnh $u$ mất thời gian tỉ lệ với số bậc (degree) của $u$. Tổng thời gian để duyệt qua tất cả các danh sách kề là $O(E)$ (với đồ thị vô hướng, mỗi cạnh $(u,v)$ xuất hiện 2 lần trong danh sách kề: $v$ trong adj[u] và $u$ trong adj[v]). Thêm vào đó là thời gian thăm mỗi đỉnh $O(V)$. Do đó, độ phức tạp thời gian của DFS là $O(V + E)$, trong đó $V$ là số đỉnh và $E$ là số cạnh. Đây là hiệu quả tối ưu cho việc duyệt toàn bộ đồ thị.
Độ phức tạp không gian: DFS sử dụng không gian cho mảng visited là $O(V)$. Không gian cho ngăn xếp đệ quy (hoặc ngăn xếp tường minh nếu triển khai phi đệ quy) có thể lên tới $O(V)$ trong trường hợp xấu nhất (đồ thị là một đường thẳng dài), nhưng trung bình có thể nhỏ hơn nhiều tùy cấu trúc đồ thị. Tổng cộng, độ phức tạp không gian là $O(V)$.

Ứng dụng Của Thuật toán DFS

DFS không chỉ là một thuật toán duyệt đơn thuần; cách nó khám phá đồ thị làm cho nó trở thành công cụ hữu ích cho nhiều bài toán khác nhau.

1. Tìm đường đi giữa hai đỉnh

DFS có thể được sử dụng để kiểm tra xem có tồn tại đường đi từ đỉnh $s$ đến đỉnh $t$ trong đồ thị hay không. Nếu đỉnh $t$ được thăm trong quá trình DFS bắt đầu từ $s$, thì có đường đi.

#include <iostream>
#include <vector>

// Sử dụng vector<vector<int>> cho danh sách kề
std::vector<std::vector<int>> adj_path;
// Mảng boolean cho đỉnh đã thăm
std::vector<bool> visited_path;

// Hàm DFS tìm đường đi
bool findPathDFS(int u, int target) {
    // 1. Đánh dấu đỉnh hiện tại là đã thăm
    visited_path[u] = true;

    // Nếu đỉnh hiện tại là đỉnh đích, chúng ta đã tìm thấy đường đi
    if (u == target) {
        return true;
    }

    // 2. Duyệt qua các đỉnh kề
    for (int v : adj_path[u]) {
        // Nếu đỉnh kề v chưa được thăm
        if (!visited_path[v]) {
            // Gọi đệ quy DFS cho v. Nếu cuộc gọi đệ quy tìm thấy đích...
            if (findPathDFS(v, target)) {
                return true; // ...thì trả về true ngay lập tức (tìm thấy đường đi)
            }
        }
    }

    // 3. Nếu đã duyệt hết các đỉnh kề mà không tìm thấy đích từ nhánh này
    return false; // Trả về false
}

int main() {
    // Đồ thị ví dụ
    // 0 -> 1 -> 3 -> 5
    // |    ^
    // v    |
    // 2 -> 4
    int numVertices = 6;
    adj_path.resize(numVertices);
    // Khởi tạo visited_path cho mỗi lần kiểm tra
    // visited_path.assign(numVertices, false); // Sẽ reset trong main

    // Thêm cạnh (đồ thị có hướng)
    adj_path[0].push_back(1);
    adj_path[0].push_back(2);
    adj_path[1].push_back(3);
    adj_path[2].push_back(4);
    adj_path[3].push_back(5);
    adj_path[4].push_back(1); // Cạnh ngược

    int start = 0;
    int target1 = 5; // Có đường: 0 -> 1 -> 3 -> 5
    int target2 = 4; // Có đường: 0 -> 2 -> 4
    int target3 = 0; // Có đường (chính nó)
    int target4 = 10; // Không tồn tại

    // Kiểm tra đường đi từ 0 đến 5
    visited_path.assign(numVertices, false); // Reset trước mỗi lần kiểm tra
    std::cout << "Co duong di tu " << start << " den " << target1 << "? " << (findPathDFS(start, target1) ? "Co" : "Khong") << std::endl;

    // Kiểm tra đường đi từ 0 đến 4
    visited_path.assign(numVertices, false); // Reset
    std::cout << "Co duong di tu " << start << " den " << target2 << "? " << (findPathDFS(start, target2) ? "Co" : "Khong") << std::endl;

    // Kiểm tra đường đi từ 0 đến 0
    visited_path.assign(numVertices, false); // Reset
    std::cout << "Co duong di tu " << start << " den " << target3 << "? " << (findPathDFS(start, target3) ? "Co" : "Khong") << std::endl;

    // Kiểm tra đường đi từ 0 đến 10 (không tồn tại)
    visited_path.assign(numVertices, false); // Reset
     // Cẩn thận với đỉnh target không tồn tại trong đồ thị
     if (target4 >= numVertices) {
         std::cout << "Dinh dich " << target4 << " khong ton tai trong do thi." << std::endl;
     } else {
        std::cout << "Co duong di tu " << start << " den " << target4 << "? " << (findPathDFS(start, target4) ? "Co" : "Khong") << std::endl;
     }


    return 0;
}

Giải thích Code:

Hàm findPathDFS tương tự như dfs cơ bản nhưng nó trả về bool.
Nếu đỉnh hiện tại u chính là đỉnh target, chúng ta trả về true ngay lập tức vì đã tìm thấy đường đi.
Trong vòng lặp duyệt đỉnh kề, nếu cuộc gọi đệ quy findPathDFS(v, target) trả về true, điều đó có nghĩa là đích được tìm thấy từ đỉnh v, do đó chúng ta cũng trả về true từ hàm hiện tại (không cần khám phá thêm các đỉnh kề khác của u).
Nếu vòng lặp kết thúc mà không tìm thấy đích từ bất kỳ đỉnh kề nào, hàm trả về false.
Quan trọng là phải reset vector visited_path về trạng thái false cho tất cả các đỉnh trước mỗi lần gọi findPathDFS nếu bạn muốn kiểm tra nhiều cặp đỉnh (start, target) khác nhau trên cùng một đồ thị.

2. Tìm và Đếm các Thành phần Liên thông (Connected Components)

Trong đồ thị vô hướng, các thành phần liên thông là các tập hợp con các đỉnh mà giữa bất kỳ hai đỉnh nào trong tập con đó đều có đường đi. DFS rất hiệu quả trong việc xác định các thành phần liên thông. Chúng ta chỉ cần lặp qua tất cả các đỉnh của đồ thị. Nếu gặp một đỉnh chưa được thăm, đó là khởi đầu của một thành phần liên thông mới. Chúng ta thực hiện DFS từ đỉnh đó để đánh dấu tất cả các đỉnh trong thành phần liên thông đó là đã thăm, sau đó tăng bộ đếm thành phần liên thông.

#include <iostream>
#include <vector>

// Sử dụng vector<vector<int>> cho danh sách kề
std::vector<std::vector<int>> adj_cc;
// Mảng boolean cho đỉnh đã thăm
std::vector<bool> visited_cc;

// Hàm DFS để đánh dấu tất cả đỉnh trong một thành phần liên thông
void dfs_cc(int u) {
    visited_cc[u] = true;
    // Duyệt qua các đỉnh kề
    for (int v : adj_cc[u]) {
        // Nếu đỉnh kề v chưa được thăm, gọi đệ quy
        if (!visited_cc[v]) {
            dfs_cc(v);
        }
    }
}

int main() {
    // Đồ thị ví dụ có 3 thành phần liên thông
    // Component 1: 0-1-2
    // Component 2: 3-4
    // Component 3: 5-6-7
    int numVertices = 8;
    adj_cc.resize(numVertices);
    visited_cc.resize(numVertices, false); // Khởi tạo tất cả là chưa thăm

    // Thêm cạnh (đồ thị vô hướng)
    // Component 1
    adj_cc[0].push_back(1); adj_cc[1].push_back(0);
    adj_cc[1].push_back(2); adj_cc[2].push_back(1);

    // Component 2
    adj_cc[3].push_back(4); adj_cc[4].push_back(3);

    // Component 3
    adj_cc[5].push_back(6); adj_cc[6].push_back(5);
    adj_cc[6].push_back(7); adj_cc[7].push_back(6);


    int connected_components = 0;
    // Lặp qua tất cả các đỉnh trong đồ thị
    for (int i = 0; i < numVertices; ++i) {
        // Nếu đỉnh i chưa được thăm, nó là đỉnh bắt đầu của một thành phần liên thông mới
        if (!visited_cc[i]) {
            // Bắt đầu DFS từ đỉnh i để thăm tất cả các đỉnh trong thành phần này
            dfs_cc(i);
            // Tăng bộ đếm thành phần liên thông
            connected_components++;
        }
    }

    std::cout << "So luong thanh phan lien thong: " << connected_components << std::endl; // Kết quả mong đợi: 3

    return 0;
}

Giải thích Code:

Hàm dfs_cc giống hệt hàm DFS cơ bản, mục đích của nó chỉ là để đánh dấu tất cả các đỉnh trong một thành phần liên thông là đã thăm.
Trong main, chúng ta có một vòng lặp chính chạy từ đỉnh 0 đến numVertices - 1.
Bên trong vòng lặp, chúng ta kiểm tra if (!visited_cc[i]). Nếu đúng, điều này có nghĩa là đỉnh i thuộc về một thành phần liên thông mà chúng ta chưa khám phá.
Chúng ta gọi dfs_cc(i) để khám phá toàn bộ thành phần đó.
Ngay sau khi gọi dfs_cc(i) và nó hoàn thành, tất cả các đỉnh trong thành phần liên thông chứa i đều đã được đánh dấu là visited_cc = true. Chúng ta tăng bộ đếm connected_components.
Vòng lặp tiếp tục. Khi nó gặp lại một đỉnh đã được thăm (thuộc về một thành phần đã đếm), điều kiện !visited_cc[i] sẽ là false, và chúng ta bỏ qua đỉnh đó.

3. Sắp xếp Tô-pô (Topological Sort)

Trong đồ thị có hướng không chứa chu trình (Directed Acyclic Graph - DAG), sắp xếp tô-pô là một cách sắp xếp các đỉnh theo thứ tự sao cho với mỗi cạnh có hướng $(u, v)$, đỉnh $u$ luôn đứng trước đỉnh $v$ trong thứ tự sắp xếp. DFS có thể được sử dụng để thực hiện sắp xếp tô-pô bằng cách ghi lại thứ tự các đỉnh kết thúc (finish time) quá trình DFS. Thứ tự tô-pô là danh sách các đỉnh theo thứ tự thời gian kết thúc giảm dần.

4. Phát hiện Chu trình (Cycle Detection)

DFS có thể phát hiện chu trình trong cả đồ thị vô hướng và có hướng.

Trong đồ thị vô hướng: Chu trình được phát hiện khi DFS gặp một đỉnh đã được thăm (visited = true) nhưng đỉnh đó không phải là đỉnh cha trực tiếp trong cây DFS hiện tại.
Trong đồ thị có hướng: Chu trình được phát hiện khi DFS gặp một đỉnh đã được thăm và đỉnh đó vẫn đang nằm trên ngăn xếp đệ quy (đang trong quá trình xử lý, chưa kết thúc). Chúng ta cần thêm một mảng/tập hợp thứ hai để theo dõi các đỉnh đang trong "đường đi" DFS hiện tại.

5. Tìm Thành phần Liên thông Mạnh (Strongly Connected Components - SCC)

Trong đồ thị có hướng, thành phần liên thông mạnh là một tập hợp con các đỉnh mà giữa bất kỳ hai đỉnh nào trong tập con đó đều có đường đi hai chiều. Thuật toán Kosaraju hoặc thuật toán Tarjan sử dụng DFS làm nền tảng để tìm các SCC.

6. Giải Mê Cung hoặc các bài toán Backtracking

Cơ chế đi sâu và quay lui tự nhiên của DFS làm cho nó rất phù hợp để giải các bài toán tìm kiếm lời giải bằng cách thử từng khả năng và quay lui khi gặp bế tắc, ví dụ như giải mê cung, bài toán N-Queens, Sudoku Solver, v.v.

Khi Nào Nên Sử Dụng DFS?

Khi bạn cần duyệt toàn bộ các đỉnh hoặc cạnh của đồ thị.
Khi bạn muốn tìm đường đi bất kỳ giữa hai đỉnh (không quan tâm đến độ dài đường đi).
Khi bạn cần khám phá cấu trúc phân cấp hoặc cây của đồ thị.
Khi bạn cần các ứng dụng như phát hiện chu trình, tìm thành phần liên thông, sắp xếp tô-pô (trên DAG).
Đối với các bài toán tìm kiếm lời giải bằng cách thử và sai (backtracking).

Bài tập ví dụ:

[Graph]. Đếm số thành phần liên thông

Cho đồ thị vô hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Hãy đếm số thành phần liên thông của đồ thị.

Input Format

Dòng đầu tiên là 2 số n và m, tương ứng với số lượng đỉnh, cạnh của đồ thị. Các đỉnh của đồ thị được đánh số từ 1 tới n. m dòng tiếp theo mỗi dòng chứa đỉnh u, v (u != v) tương ứng với một cạnh của đồ thị. (1<=n<=1000; 1<=m<=n*(n-1)/2)

Constraints

Output Format

In ra số thành phần liên thông của đồ thị

Ví dụ:

Dữ liệu vào

Dữ liệu ra

Hướng dẫn giải bài "Đếm số thành phần liên thông" bằng C++ (không code hoàn chỉnh):

Biểu diễn đồ thị: Sử dụng danh sách kề (adjacency list) để lưu trữ đồ thị. Dùng std::vector<std::vector<int>> trong C++. Kích thước của vector ngoài là n + 1 để dễ xử lý đỉnh từ 1 đến n.
Đọc input: Đọc n, m. Sau đó đọc m cạnh. Với mỗi cạnh (u, v), thêm v vào danh sách kề của u và thêm u vào danh sách kề của v (vì đồ thị vô hướng).
Theo dõi đỉnh đã thăm: Sử dụng một mảng hoặc std::vector<bool> có kích thước n + 1 để đánh dấu các đỉnh đã được thăm trong quá trình duyệt. Khởi tạo tất cả là false.
Duyệt đồ thị và đếm: Khởi tạo biến count = 0. Lặp qua các đỉnh từ 1 đến n.
- Nếu đỉnh hiện tại i chưa được thăm (visited[i] là false):
  - Tăng biến đếm count lên 1 (vì tìm thấy một thành phần liên thông mới).
  - Bắt đầu một thuật toán duyệt đồ thị (DFS hoặc BFS) từ đỉnh i.
  - Trong quá trình duyệt (DFS hoặc BFS), đánh dấu tất cả các đỉnh mà thuật toán thăm được trong thành phần liên thông này là đã thăm (visited[j] = true).
Thuật toán duyệt (DFS hoặc BFS):
- Sử dụng DFS (Đệ quy hoặc dùng Stack): Hàm DFS(u, adj, visited) sẽ đánh dấu u là đã thăm, sau đó duyệt qua tất cả các đỉnh v kề với u. Nếu v chưa thăm, gọi đệ quy DFS(v, adj, visited).
- Sử dụng BFS (Dùng Queue): Bỏ đỉnh bắt đầu vào hàng đợi và đánh dấu đã thăm. Trong khi hàng đợi còn phần tử, lấy một đỉnh u ra, duyệt qua các đỉnh v kề với u. Nếu v chưa thăm, đánh dấu v đã thăm và bỏ v vào hàng đợi.
Kết quả: Sau khi lặp hết qua tất cả các đỉnh từ 1 đến n, biến count sẽ chứa số thành phần liên thông. In ra giá trị này.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.