Khóa học CTDL và GT

Bài 19.5: Bài tập cơ bản về đồ thị đặc biệt

Chào mừng bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật!

Sau khi đã làm quen với các khái niệm cơ bản về đồ thị, cách biểu diễn, và các thuật toán duyệt kinh điển như BFS và DFS, giờ là lúc chúng ta áp dụng những kiến thức đó vào việc giải quyết các bài toán thực tế hơn một chút. Phần lớn các bài toán đồ thị phức tạp đều được xây dựng dựa trên những khối kiến thức nền tảng này. Hôm nay, chúng ta sẽ cùng nhau đi qua một số bài tập cơ bản xoay quanh việc sử dụng BFS/DFS và nhận diện các đặc điểm của đồ thị, mà đôi khi ta gọi là "đồ thị đặc biệt" trong ngữ cảnh của những tính chất đơn giản.

Mục tiêu của bài viết này không phải là giới thiệu các loại đồ thị đặc biệt phức tạp (như đồ thị phẳng, đồ thị hoàn chỉnh, v.v.) mà là cách sử dụng các kỹ thuật duyệt cơ bản để kiểm tra các tính chất đặc trưng của đồ thị, giúp phân loại hoặc giải quyết các bài toán nền tảng. Hãy coi đây là những "bài tập cơ bản" giúp bạn củng cố và vận dụng kiến thức về đồ thị.

Chúng ta sẽ đi sâu vào một vài dạng bài tập thường gặp:

1. Kiểm tra sự liên thông giữa hai đỉnh.
2. Đếm số lượng thành phần liên thông.
3. Phát hiện chu trình trong đồ thị.
4. Kiểm tra xem một đồ thị có phải là cây hay không.

Mỗi bài tập sẽ đi kèm với ý tưởng giải quyết và ví dụ minh họa bằng C++.

Bài Tập 1: Kiểm Tra Sự Liên Thông Giữa Hai Đỉnh

Đây là một trong những bài tập cơ bản nhất về đồ thị, giúp bạn thực hành ngay với thuật toán duyệt. Hai đỉnh u và v được coi là liên thông nếu có một đường đi từ u đến v (hoặc ngược lại trong đồ thị vô hướng).

Ý tưởng: Cách đơn giản nhất để kiểm tra điều này là sử dụng thuật toán Duyệt theo chiều sâu (DFS) hoặc Duyệt theo chiều rộng (BFS) bắt đầu từ đỉnh u. Nếu trong quá trình duyệt, ta thăm được đỉnh v, thì có nghĩa là có đường đi từ u đến v, và hai đỉnh này liên thông.

Code C++ Minh Họa (Sử dụng DFS):

Đầu tiên, giả định đồ thị được biểu diễn bằng danh sách kề (adjacency list).

#include <iostream>
#include <vector>
#include <queue> // Có thể dùng BFS thay DFS nếu muốn

using namespace std;

// Hàm DFS để kiểm tra sự liên thông
void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true; // Đánh dấu đỉnh hiện tại đã thăm

    // Duyệt qua tất cả các đỉnh kề với u
    for (int v : adj[u]) {
        // Nếu đỉnh kề chưa được thăm, gọi đệ quy DFS
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

// Hàm kiểm tra liên thông giữa hai đỉnh start_node và end_node
bool areConnected(int n, const vector<vector<int>>& adj, int start_node, int end_node) {
    // Đảm bảo các đỉnh đầu vào hợp lệ
    if (start_node < 0 || start_node >= n || end_node < 0 || end_node >= n) {
        return false; // Đỉnh không hợp lệ
    }

    vector<bool> visited(n, false); // Mảng visited để theo dõi các đỉnh đã thăm

    // Bắt đầu DFS từ đỉnh start_node
    dfs(start_node, adj, visited);

    // Sau khi DFS kết thúc, kiểm tra xem end_node đã được thăm hay chưa
    return visited[end_node];
}

int main() {
    int n = 6; // Số đỉnh (đánh số từ 0 đến n-1)
    // Biểu diễn đồ thị bằng danh sách kề
    // Ví dụ: Đồ thị có các cạnh (0, 1), (0, 2), (3, 4)
    vector<vector<int>> adj(n);
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[3].push_back(4); adj[4].push_back(3);
    adj[4].push_back(5); adj[5].push_back(4);


    // Kiểm tra liên thông
    cout << "Is 0 and 1 connected? " << (areConnected(n, adj, 0, 1) ? "Yes" : "No") << endl; // Expected: Yes
    cout << "Is 0 and 4 connected? " << (areConnected(n, adj, 0, 4) ? "Yes" : "No") << endl; // Expected: No
    cout << "Is 3 and 5 connected? " << (areConnected(n, adj, 3, 5) ? "Yes" : "No") << endl; // Expected: Yes

    return 0;
}

Giải thích Code:

• Chúng ta sử dụng một vector<vector<int>> adj để lưu trữ danh sách kề. adj[i] chứa danh sách các đỉnh kề với đỉnh i. Với đồ thị vô hướng, cạnh (u, v) được thêm vào cả adj[u] và adj[v].
• Hàm dfs(u, adj, visited) là thuật toán DFS kinh điển. Nó nhận đỉnh hiện tại u, danh sách kề adj và mảng visited. Nó đánh dấu đỉnh u là đã thăm, sau đó đệ quy gọi dfs cho tất cả các đỉnh kề v mà chưa được thăm.
• Hàm areConnected(n, adj, start_node, end_node) là hàm chính để kiểm tra.
  • Nó khởi tạo mảng visited gồm n phần tử, tất cả đều là false.
  • Nó gọi dfs bắt đầu từ start_node.
  • Sau khi dfs hoàn thành, mảng visited sẽ đánh dấu tất cả các đỉnh reachable (có thể đến được) từ start_node.
  • Cuối cùng, nó trả về giá trị của visited[end_node]. Nếu true, nghĩa là end_node đã được thăm từ start_node, tức là chúng liên thông.

Bài tập này rất đơn giản nhưng là bước đệm quan trọng để bạn làm quen lại với việc cài đặt BFS/DFS trên code.

Bài Tập 2: Đếm Số Lượng Thành Phần Liên Thông

Đồ thị vô hướng có thể được chia thành các thành phần liên thông (connected components). Mỗi thành phần liên thông là một tập hợp các đỉnh mà giữa bất kỳ hai đỉnh nào trong tập hợp đó cũng tồn tại một đường đi, và tập hợp này là lớn nhất có tính chất đó. Nói cách khác, các thành phần liên thông là các "mảnh" riêng biệt của đồ thị, không có cạnh nào nối giữa các mảnh khác nhau.

Ý tưởng: Để đếm số lượng thành phần liên thông, chúng ta có thể lặp qua tất cả các đỉnh của đồ thị. Nếu gặp một đỉnh mà chưa được thăm, điều đó có nghĩa là đỉnh này thuộc về một thành phần liên thông mới mà chúng ta chưa khám phá. Chúng ta sẽ bắt đầu một thuật toán duyệt (DFS hoặc BFS) từ đỉnh này để thăm hết tất cả các đỉnh trong cùng thành phần liên thông với nó. Sau khi quá trình duyệt kết thúc, tất cả các đỉnh trong thành phần liên thông đó sẽ được đánh dấu là đã thăm. Chúng ta tăng bộ đếm số lượng thành phần liên thông lên 1 và tiếp tục vòng lặp tìm kiếm đỉnh chưa thăm khác.

Code C++ Minh Họa (Sử dụng DFS):

Tái sử dụng hàm dfs từ bài tập 1.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// Hàm DFS để thăm tất cả các đỉnh trong một thành phần liên thông
void dfs_component(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true; // Đánh dấu đỉnh hiện tại đã thăm
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs_component(v, adj, visited);
        }
    }
}

// Hàm đếm số lượng thành phần liên thông
int countConnectedComponents(int n, const vector<vector<int>>& adj) {
    vector<bool> visited(n, false); // Mảng theo dõi các đỉnh đã thăm
    int count = 0; // Bộ đếm số thành phần liên thông

    // Lặp qua tất cả các đỉnh
    for (int i = 0; i < n; ++i) {
        // Nếu đỉnh i chưa được thăm, nó bắt đầu một thành phần liên thông mới
        if (!visited[i]) {
            dfs_component(i, adj, visited); // Thăm hết các đỉnh trong thành phần này
            count++; // Tăng bộ đếm
        }
    }
    return count;
}

int main() {
    int n = 6; // Số đỉnh (0-5)
    vector<vector<int>> adj(n);

    // Thành phần 1: 0, 1, 2
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);

    // Thành phần 2: 3, 4, 5
    adj[3].push_back(4); adj[4].push_back(3);
    adj[4].push_back(5); adj[5].push_back(4);


    // Đếm số thành phần liên thông
    cout << "Number of connected components: " << countConnectedComponents(n, adj) << endl; // Expected: 2

    // Thêm một đỉnh cô lập
    int n2 = 7; // Đỉnh 6 cô lập
    vector<vector<int>> adj2(n2);
    // Copy các cạnh cũ
    for(int i = 0; i < 6; ++i) {
        adj2[i] = adj[i];
    }
    // adj2[6] rỗng (đỉnh 6 cô lập)

    cout << "Number of connected components (with isolated node): " << countConnectedComponents(n2, adj2) << endl; // Expected: 3 (0-1-2, 3-4-5, 6)


    return 0;
}

Giải thích Code:

• Hàm dfs_component về cơ bản giống với hàm dfs trước đó, chỉ là được đặt tên khác để rõ ràng hơn về mục đích sử dụng trong bài toán này. Nó dùng để thăm tất cả các đỉnh trong một "nhóm" liên thông bắt đầu từ đỉnh u.
• Hàm countConnectedComponents(n, adj) là logic chính.
  • Nó duy trì mảng visited và biến count.
  • Nó duyệt qua từng đỉnh i từ 0 đến n-1.
  • Nếu visited[i] là false, điều này báo hiệu rằng đỉnh i chưa được thăm và nó thuộc về một thành phần liên thông mới. Ta gọi dfs_component(i, adj, visited) để đánh dấu tất cả các đỉnh trong thành phần này là đã thăm, và tăng count lên 1.
  • Nếu visited[i] là true, đỉnh i đã thuộc về một thành phần liên thông đã được xử lý trước đó, nên ta bỏ qua.
• Kết quả cuối cùng là giá trị của count.

Bài tập này thể hiện cách sử dụng thuật toán duyệt để khám phá cấu trúc phân mảnh của đồ thị vô hướng.

Bài Tập 3: Phát Hiện Chu Trình Đơn Giản Trong Đồ Thị Vô Hướng

Chu trình (cycle) là một đường đi bắt đầu và kết thúc tại cùng một đỉnh, không đi qua bất kỳ cạnh nào hai lần và chỉ đi qua các đỉnh trung gian một lần. Phát hiện chu trình là một bài toán quan trọng, đặc biệt khi làm việc với các cấu trúc như cây (tree), mà chúng ta sẽ nói đến sau.

Ý tưởng: Chúng ta có thể sử dụng DFS để phát hiện chu trình trong đồ thị vô hướng. Khi thực hiện DFS, chúng ta đi từ một đỉnh u đến đỉnh kề v. Nếu đỉnh v đã được thăm và v không phải là đỉnh cha của u trong cây DFS hiện tại, điều đó chứng tỏ chúng ta đã tìm thấy một cạnh nối u với một đỉnh v đã thăm ở "cao hơn" trong cây DFS (hoặc ở một nhánh khác đã thăm), tạo thành một chu trình.

Chúng ta cần theo dõi không chỉ các đỉnh đã thăm (visited) mà còn cả đỉnh cha (parent) của đỉnh hiện tại trong quá trình DFS để phân biệt cạnh "đi lên" trong cây DFS (không tạo chu trình) với các cạnh khác (có thể tạo chu trình).

Code C++ Minh Họa (Sử dụng DFS):

#include <iostream>
#include <vector>

using namespace std;

// Hàm DFS để phát hiện chu trình
// u: đỉnh hiện tại
// parent: đỉnh cha của u trong quá trình DFS
// adj: danh sách kề
// visited: mảng theo dõi đỉnh đã thăm
// recursionStack: (Không cần thiết trong đồ thị vô hướng, dùng cho đồ thị có hướng)
// hasCycle: biến boolean để đánh dấu nếu tìm thấy chu trình
bool dfs_cycle_undirected(int u, int parent, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true; // Đánh dấu đỉnh u đã thăm

    // Duyệt qua tất cả các đỉnh kề v của u
    for (int v : adj[u]) {
        // Nếu đỉnh kề v chưa được thăm
        if (!visited[v]) {
            // Tiếp tục DFS từ v. Nếu đệ quy trả về true (tìm thấy chu trình), thì hàm hiện tại cũng trả về true
            if (dfs_cycle_undirected(v, u, adj, visited)) {
                return true; // Chu trình được phát hiện ở nhánh con
            }
        }
        // Nếu đỉnh kề v đã được thăm VÀ v không phải là đỉnh cha của u
        else if (v != parent) {
            // Phát hiện chu trình!
            return true;
        }
    }
    // Nếu duyệt hết các đỉnh kề mà không phát hiện chu trình
    return false;
}

// Hàm kiểm tra toàn bộ đồ thị có chu trình hay không
bool containsCycleUndirected(int n, const vector<vector<int>>& adj) {
    vector<bool> visited(n, false); // Mảng theo dõi đỉnh đã thăm

    // Lặp qua tất cả các đỉnh. Đảm bảo kiểm tra cả các thành phần liên thông khác nhau.
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            // Gọi DFS bắt đầu từ đỉnh i với cha ban đầu là -1 (hoặc bất kỳ giá trị không hợp lệ nào)
            if (dfs_cycle_undirected(i, -1, adj, visited)) {
                return true; // Tìm thấy chu trình trong thành phần liên thông này
            }
        }
    }
    // Nếu duyệt hết tất cả các thành phần mà không tìm thấy chu trình nào
    return false;
}

int main() {
    int n = 6; // Số đỉnh (0-5)

    // Đồ thị có chu trình: 0-1-2-0
    vector<vector<int>> adj_with_cycle(n);
    adj_with_cycle[0].push_back(1); adj_with_cycle[1].push_back(0);
    adj_with_cycle[1].push_back(2); adj_with_cycle[2].push_back(1);
    adj_with_cycle[2].push_back(0); adj_with_cycle[0].push_back(2);
    // Các đỉnh còn lại (3, 4, 5) cô lập hoặc tạo thành các thành phần khác không có chu trình

    cout << "Graph with cycle (0-1-2-0): Contains cycle? "
         << (containsCycleUndirected(n, adj_with_cycle) ? "Yes" : "No") << endl; // Expected: Yes

    // Đồ thị không có chu trình (một "rừng" gồm nhiều cây): 0-1, 0-2, 3-4, 4-5
    vector<vector<int>> adj_no_cycle(n);
    adj_no_cycle[0].push_back(1); adj_no_cycle[1].push_back(0);
    adj_no_cycle[0].push_back(2); adj_no_cycle[2].push_back(0);
    adj_no_cycle[3].push_back(4); adj_no_cycle[4].push_back(3);
    adj_no_cycle[4].push_back(5); adj_no_cycle[5].push_back(4);


    cout << "Graph without cycle (a forest): Contains cycle? "
         << (containsCycleUndirected(n, adj_no_cycle) ? "Yes" : "No") << endl; // Expected: No


    return 0;
}

Giải thích Code:

• Hàm dfs_cycle_undirected(u, parent, adj, visited) là trái tim của thuật toán. Nó nhận thêm tham số parent để biết đỉnh nào đã gọi đến đỉnh u này.
• Khi duyệt qua các đỉnh kề v của u:
  • Nếu v chưa được thăm (!visited[v]), ta tiếp tục DFS từ v, coi u là cha của v. Nếu cuộc gọi đệ quy này trả về true (nghĩa là tìm thấy chu trình ở đâu đó sâu hơn), thì ta cũng trả về true ngay lập tức.
  • Nếu v đã được thăm (visited[v]) và v không phải là đỉnh cha parent của u, thì ta đã tìm thấy một cạnh nối u với một đỉnh đã thăm mà không phải là cạnh quay ngược lại đỉnh cha trực tiếp. Đây chính là dấu hiệu của một chu trình. Ta trả về true.
• Nếu vòng lặp kết thúc mà không tìm thấy trường hợp nào như vậy, nghĩa là không có chu trình đi qua đỉnh u và các nhánh con của nó. Hàm trả về false.
• Hàm containsCycleUndirected(n, adj) lặp qua tất cả các đỉnh để đảm bảo kiểm tra cả những thành phần liên thông không chứa đỉnh 0. Đối với mỗi đỉnh chưa thăm, nó gọi dfs_cycle_undirected để bắt đầu quá trình kiểm tra chu trình từ đỉnh đó, với đỉnh cha ban đầu là -1 (một giá trị không thể là đỉnh thực).

Kỹ thuật truyền đỉnh cha này là quan trọng để phân biệt cạnh tạo chu trình với cạnh của cây DFS.

Bài Tập 4: Kiểm Tra Đồ Thị Có Phải Là Cây Không

Bây giờ, chúng ta đến với một dạng "đồ thị đặc biệt" khá quen thuộc trong các bài tập cơ bản: Cây (Tree). Trong lý thuyết đồ thị, một cây là một đồ thị vô hướng, liên thông và không chứa chu trình. Một cách định nghĩa khác tương đương: đồ thị vô hướng có N đỉnh và N-1 cạnh, đồng thời không chứa chu trình. Hoặc: đồ thị vô hướng có N đỉnh và N-1 cạnh, đồng thời liên thông. Chỉ cần thỏa mãn hai trong ba tính chất (liên thông, không chu trình, N-1 cạnh với N đỉnh) thì đồ thị đó là cây.

Dựa vào các bài tập trước, chúng ta có thể kết hợp các kỹ thuật để kiểm tra xem một đồ thị có phải là cây hay không.

Ý tưởng: Để kiểm tra một đồ thị vô hướng có phải là cây NẾU TA CHỈ BIẾT SỐ ĐỈNH VÀ DANH SÁCH CẠNH (chứ không biết trước số cạnh có phải là N-1 không), ta cần kiểm tra hai tính chất:

1. Liên thông: Tất cả các đỉnh có thuộc cùng một thành phần liên thông không? Ta có thể kiểm tra bằng cách chạy DFS/BFS từ một đỉnh bất kỳ và xem có thăm được tất cả các đỉnh còn lại không.
2. Không chu trình: Đồ thị có chứa chu trình hay không? Ta sử dụng kỹ thuật phát hiện chu trình từ bài tập 3.

Một đồ thị vô hướng với n đỉnh là cây khi và chỉ khi nó liên thông và không chứa chu trình. (Chú ý: Định nghĩa cây đôi khi yêu cầu số cạnh là n-1, nhưng với hai điều kiện liên thông và không chu trình thì số cạnh tự động là n-1).

Code C++ Minh Họa (Kết hợp kiểm tra liên thông và không chu trình):

Tái sử dụng hàm dfs_cycle_undirected từ bài tập 3, nhưng điều chỉnh một chút để có thể kiểm tra tất cả các đỉnh có được thăm hay không sau một lần duyệt.

#include <iostream>
#include <vector>
#include <numeric> // For std::all_of

using namespace std;

// Hàm DFS để kiểm tra chu trình và đếm số đỉnh đã thăm
// Nó trả về true nếu tìm thấy chu trình, false nếu không
bool dfs_check_tree(int u, int parent, const vector<vector<int>>& adj, vector<bool>& visited, int& visited_count) {
    visited[u] = true;
    visited_count++; // Tăng bộ đếm đỉnh đã thăm

    for (int v : adj[u]) {
        if (!visited[v]) {
            // Nếu nhánh con tìm thấy chu trình, trả về true
            if (dfs_check_tree(v, u, adj, visited, visited_count)) {
                return true;
            }
        } else if (v != parent) {
            // Tìm thấy chu trình
            return true;
        }
    }
    // Không tìm thấy chu trình trong nhánh này
    return false;
}

// Hàm kiểm tra xem đồ thị có phải là cây không
bool isTree(int n, const vector<vector<int>>& adj) {
    if (n == 0) return true; // Đồ thị rỗng được coi là cây (với 0 đỉnh, 0 cạnh)

    vector<bool> visited(n, false);
    int visited_count = 0; // Biến đếm số đỉnh được thăm từ lần DFS đầu tiên

    // 1. Kiểm tra xem có chu trình không và bắt đầu đếm số đỉnh liên thông từ đỉnh 0
    // Bắt đầu DFS từ đỉnh 0 (hoặc bất kỳ đỉnh nào)
    // Hàm này sẽ trả về true nếu có chu trình
    if (dfs_check_tree(0, -1, adj, visited, visited_count)) {
        return false; // Có chu trình, không phải cây
    }

    // 2. Sau khi DFS từ đỉnh 0 kết thúc, kiểm tra xem tất cả các đỉnh đã được thăm chưa
    // Nếu số đỉnh đã thăm bằng tổng số đỉnh n, nghĩa là đồ thị liên thông.
    bool is_connected = (visited_count == n);

    // Đồ thị là cây nếu nó không có chu trình VÀ liên thông
    return is_connected;

    // *Lưu ý:* Một cách kiểm tra thứ ba là đếm số cạnh.
    // Đồ thị vô hướng có n đỉnh là cây <=> nó liên thông và có n-1 cạnh
    // hoặc <=> nó không có chu trình và có n-1 cạnh.
    // Nếu bạn đã đếm số cạnh (ví dụ khi đọc input), bạn có thể kết hợp:
    // long long num_edges = 0; // Đếm số cạnh
    // for(const auto& neighbors : adj) num_edges += neighbors.size();
    // num_edges /= 2; // Đồ thị vô hướng, mỗi cạnh được đếm 2 lần

    // bool has_n_minus_1_edges = (num_edges == n - 1);
    // return (!has_cycle && is_connected); // Hoặc (!has_cycle && has_n_minus_1_edges)
    // Cách dùng visited_count == n kết hợp với không chu trình là phổ biến và đáng tin cậy.
}


int main() {
    int n = 5; // 5 đỉnh (0-4)

    // Đồ thị Cây (liên thông, không chu trình, 5 đỉnh, 4 cạnh)
    vector<vector<int>> adj_tree(n);
    adj_tree[0].push_back(1); adj_tree[1].push_back(0);
    adj_tree[0].push_back(2); adj_tree[2].push_back(0);
    adj_tree[1].push_back(3); adj_tree[3].push_back(1);
    adj_tree[2].push_back(4); adj_tree[4].push_back(2);

    cout << "Graph (is a tree): Is it a tree? "
         << (isTree(n, adj_tree) ? "Yes" : "No") << endl; // Expected: Yes

    // Đồ thị không phải cây (có chu trình 0-1-2-0)
    vector<vector<int>> adj_not_tree_cycle(n);
    adj_not_tree_cycle[0].push_back(1); adj_not_tree_cycle[1].push_back(0);
    adj_not_tree_cycle[1].push_back(2); adj_not_tree_cycle[2].push_back(1);
    adj_not_tree_cycle[2].push_back(0); adj_not_tree_cycle[0].push_back(2);
    adj_not_tree_cycle[3].push_back(4); adj_not_tree_cycle[4].push_back(3); // Thành phần khác

    cout << "Graph (has a cycle): Is it a tree? "
         << (isTree(n, adj_not_tree_cycle) ? "Yes" : "No") << endl; // Expected: No

    // Đồ thị không phải cây (không liên thông - là một "rừng")
    int n2 = 6; // 6 đỉnh
    vector<vector<int>> adj_not_tree_disconnected(n2);
    adj_not_tree_disconnected[0].push_back(1); adj_not_tree_disconnected[1].push_back(0);
    adj_not_tree_disconnected[0].push_back(2); adj_not_tree_disconnected[2].push_back(0); // Cây 0-1-2
    adj_not_tree_disconnected[3].push_back(4); adj_not_tree_disconnected[4].push_back(3);
    adj_not_tree_disconnected[4].push_back(5); adj_not_tree_disconnected[5].push_back(4); // Cây 3-4-5

    cout << "Graph (disconnected forest): Is it a tree? "
         << (isTree(n2, adj_not_tree_disconnected) ? "Yes" : "No") << endl; // Expected: No


    return 0;
}

Giải thích Code:

• Hàm dfs_check_tree kết hợp logic của dfs_cycle_undirected và việc đếm số đỉnh đã thăm. Nó nhận thêm tham chiếu visited_count để cập nhật số lượng đỉnh được thăm trong lần gọi DFS ban đầu (từ đỉnh 0).
• Nó trả về true ngay lập tức nếu tìm thấy chu trình.
• Hàm isTree(n, adj):
  • Xử lý trường hợp đặc biệt n=0 (đồ thị rỗng là cây).
  • Khởi tạo visited và visited_count.
  • Gọi dfs_check_tree từ đỉnh 0 (hoặc bất kỳ đỉnh nào). Nếu hàm này trả về true, nghĩa là có chu trình, và đồ thị không phải là cây.
  • Nếu không có chu trình, ta kiểm tra xem visited_count có bằng n hay không. Nếu có, nghĩa là tất cả các đỉnh đều được thăm từ đỉnh 0, tức là đồ thị liên thông.
  • Đồ thị chỉ là cây khi không có chu trình và liên thông.

Bài tập này cho thấy sức mạnh của việc kết hợp các thuật toán cơ bản để kiểm tra các thuộc tính phức tạp hơn của đồ thị. Việc hiểu rõ định nghĩa của "cây" và cách kiểm tra nó bằng BFS/DFS là cực kỳ quan trọng cho các bài toán sau này.

Bài tập ví dụ:

Lịch Học

Trong một buổi thảo luận về triết học, FullHouse Dev đã đặt ra câu hỏi về trật tự và logic trong việc sắp xếp kiến thức. Họ nhận ra rằng việc học tập cũng giống như xây dựng một tòa nhà - cần phải có nền móng vững chắc trước khi xây các tầng cao hơn. Từ đó, họ quyết định áp dụng tư duy này vào việc sắp xếp một lịch học hợp lý.

Bài toán

FullHouse Dev cần hoàn thành \(n\) khóa học. Có \(m\) yêu cầu tiên quyết dạng "khóa học a phải được hoàn thành trước khóa học b". Nhiệm vụ là tìm ra một thứ tự để có thể hoàn thành tất cả các khóa học.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng khóa học và số lượng yêu cầu tiên quyết. Các khóa học được đánh số từ \(1,2,\dots,n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): khóa học \(a\) phải được hoàn thành trước khóa học \(b\).

OUTPUT FORMAT:

• In ra một thứ tự có thể hoàn thành các khóa học. Bạn có thể in ra bất kỳ thứ tự hợp lệ nào miễn là bao gồm tất cả các khóa học.
• Nếu không có giải pháp, in ra "IMPOSSIBLE".

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)

Ví dụ

INPUT

5 3
1 2
3 1
4 5

OUTPUT

3 4 1 5 2

Giải thích

Với thứ tự này:

• Khóa học 3 được học trước khóa học 1 (thỏa mãn yêu cầu)
• Khóa học 1 được học trước khóa học 2 (thỏa mãn yêu cầu)
• Khóa học 4 được học trước khóa học 5 (thỏa mãn yêu cầu) Vì vậy, đây là một thứ tự hợp lệ để hoàn thành tất cả các khóa học. Okay, đây là hướng dẫn giải bài toán "Lịch Học" bằng C++ một cách ngắn gọn, tập trung vào ý tưởng và cấu trúc:

1. Nhận diện bài toán: Bài toán yêu cầu tìm một thứ tự tuyến tính cho các khóa học sao cho mọi yêu cầu tiên quyết (a trước b) đều được thỏa mãn. Đây chính xác là bài toán Sắp xếp Tô pô (Topological Sort) trên đồ thị có hướng.

2. Xây dựng đồ thị:

   • Xem các khóa học là các đỉnh (nodes) của đồ thị. Có n đỉnh, đánh số từ 1 đến n.
   • Mỗi yêu cầu tiên quyết a b (khóa học a phải hoàn thành trước b) được biểu diễn bằng một cạnh có hướng từ a đến b (a -> b).

3. Chọn thuật toán Sắp xếp Tô pô: Có hai thuật toán phổ biến:

   • Dựa trên DFS (Depth First Search): Tìm chu trình (cycle) trong quá trình duyệt. Thứ tự tô pô thu được bằng cách thêm đỉnh vào đầu danh sách kết quả khi hoàn thành duyệt hết nhánh con của nó.
   • Dựa trên Bậc vào (In-degree) - Thuật toán Kahn: Đây thường là lựa chọn đơn giản hơn để tìm một thứ tự và phát hiện chu trình. Ta sẽ tập trung vào thuật toán này.

4. Triển khai theo thuật toán Kahn:

   • Cấu trúc dữ liệu:
     • Một danh sách kề (adj): Lưu trữ đồ thị. adj[u] là danh sách các đỉnh v mà có cạnh u -> v. Sử dụng std::vector<std::vector<int>>.
     • Một mảng/vector in_degree: Lưu trữ bậc vào của mỗi đỉnh. in_degree[v] là số lượng các đỉnh u có cạnh u -> v. Sử dụng std::vector<int>.
     • Một hàng đợi (queue): Lưu trữ các đỉnh có bậc vào bằng 0. Sử dụng std::queue<int>.
     • Một vector để lưu kết quả: std::vector<int> result.
   • Khởi tạo:
     • Đọc n và m.
     • Khởi tạo adj và in_degree với kích thước phù hợp (ví dụ: n + 1 nếu dùng chỉ số 1-based).
     • Đọc m cặp a b. Với mỗi cặp:
       • Thêm cạnh a -> b vào danh sách kề (adj[a].push_back(b)).
       • Tăng bậc vào của b (in_degree[b]++).
     • Duyệt qua tất cả các đỉnh từ 1 đến n. Nếu in_degree[i] == 0, đưa đỉnh i vào hàng đợi queue.
   • Xử lý hàng đợi:
     • Trong khi hàng đợi không rỗng:
       • Lấy đỉnh u ra khỏi hàng đợi.
       • Thêm u vào danh sách result.
       • Đối với mỗi đỉnh v là "hàng xóm" của u (tức là có cạnh u -> v trong adj[u]):
         • Giảm bậc vào của v đi 1 (in_degree[v]--).
         • Nếu bậc vào của v trở thành 0, đưa v vào hàng đợi.
   • Kiểm tra kết quả:
     • Sau khi vòng lặp kết thúc, nếu số lượng đỉnh trong result bằng n, thì result chính là một thứ tự tô pô hợp lệ. In các đỉnh trong result.
     • Nếu số lượng đỉnh trong result nhỏ hơn n, điều đó có nghĩa là đồ thị có chu trình (không thể tìm được thứ tự tô pô). In ra "IMPOSSIBLE".

5. Cài đặt: Sử dụng các container chuẩn của C++ như vector, queue. Đảm bảo xử lý chỉ số đỉnh (1-based hoặc 0-based) một cách nhất quán.

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