Khóa học CTDL và GT

#include <iostream>
#include <vector>
#include <queue>
#include <numeric> // For std::fill

// Hàm kiểm tra tính hai phía sử dụng BFS cho một thành phần liên thông
bool isBipartiteBFS(int start_node, int V, const std::vector<std::vector<int>>& adj, std::vector<int>& color) {
    std::queue<int> q;
    q.push(start_node);
    color[start_node] = 0; // Bắt đầu tô màu đỉnh xuất phát là màu 0

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // Duyệt qua tất cả hàng xóm của đỉnh u
        for (int v : adj[u]) {
            // Nếu đỉnh v chưa được tô màu (-1)
            if (color[v] == -1) {
                // Tô màu v khác màu với u
                color[v] = 1 - color[u];
                q.push(v); // Thêm v vào hàng đợi để duyệt tiếp
            }
            // Nếu đỉnh v đã được tô màu và có CÙNG màu với u
            else if (color[v] == color[u]) {
                // Phát hiện mâu thuẫn, đồ thị không phải hai phía
                return false;
            }
        }
    }
    // Nếu duyệt xong thành phần liên thông mà không có mâu thuẫn
    return true;
}

// Hàm chính kiểm tra đồ thị hai phía (xử lý cả đồ thị không liên thông)
bool checkBipartite(int V, const std::vector<std::vector<int>>& adj) {
    // Mảng color để lưu màu của các đỉnh. -1: chưa tô màu, 0: màu 0, 1: màu 1
    std::vector<int> color(V, -1);

    // Duyệt qua tất cả các đỉnh để xử lý các thành phần liên thông
    for (int i = 0; i < V; ++i) {
        // Nếu đỉnh i chưa được tô màu, bắt đầu BFS từ đỉnh này
        if (color[i] == -1) {
            if (!isBipartiteBFS(i, V, adj, color)) {
                // Nếu một thành phần liên thông bất kỳ không phải hai phía
                return false;
            }
        }
    }

    // Nếu tất cả các thành phần liên thông đều là hai phía
    return true;
}

int main() {
    // Ví dụ 1: Đồ thị hai phía (chu trình C4)
    // 0 -- 1
    // |    |
    // 3 -- 2
    int V1 = 4;
    std::vector<std::vector<int>> adj1(V1);
    adj1[0].push_back(1); adj1[1].push_back(0);
    adj1[1].push_back(2); adj1[2].push_back(1);
    adj1[2].push_back(3); adj1[3].push_back(2);
    adj1[3].push_back(0); adj1[0].push_back(3);

    std::cout << "Example 1 (C4): " << (checkBipartite(V1, adj1) ? "Is Bipartite" : "Not Bipartite") << std::endl; // Expected: Is Bipartite

    // Ví dụ 2: Đồ thị không hai phía (chu trình C3)
    // 0 -- 1
    // |  /
    // | /
    // 2
    int V2 = 3;
    std::vector<std::vector<int>> adj2(V2);
    adj2[0].push_back(1); adj2[1].push_back(0);
    adj2[1].push_back(2); adj2[2].push_back(1);
    adj2[2].push_back(0); adj2[0].push_back(2);

    std::cout << "Example 2 (C3): " << (checkBipartite(V2, adj2) ? "Is Bipartite" : "Not Bipartite") << std::endl; // Expected: Not Bipartite

    // Ví dụ 3: Đồ thị không liên thông, cả hai thành phần đều là hai phía
    // 0 -- 1      2 -- 3
    // |    |      |    |
    // 4 -- 5      6 -- 7
    int V3 = 8;
    std::vector<std::vector<int>> adj3(V3);
    // Component 1 (C4)
    adj3[0].push_back(1); adj3[1].push_back(0);
    adj3[1].push_back(5); adj3[5].push_back(1);
    adj3[5].push_back(4); adj3[4].push_back(5);
    adj3[4].push_back(0); adj3[0].push_back(4);
    // Component 2 (C4)
    adj3[2].push_back(3); adj3[3].push_back(2);
    adj3[3].push_back(7); adj3[7].push_back(3);
    adj3[7].push_back(6); adj3[6].push_back(7);
    adj3[6].push_back(2); adj3[2].push_back(6);

    std::cout << "Example 3 (Disconnected): " << (checkBipartite(V3, adj3) ? "Is Bipartite" : "Not Bipartite") << std::endl; // Expected: Is Bipartite

    // Ví dụ 4: Đồ thị không liên thông, một thành phần là hai phía, một không
    // 0 -- 1      2 -- 3
    // |    |      |  /
    // 4 -- 5      4 -- (Note: vertex 4 is shared, this is invalid graph construction for typical adjacency list)
    // Let's create a proper example: C4 and C3 separated
    // 0 -- 1     5 -- 6
    // |    |     |  /
    // 3 -- 2     7
    int V4 = 8;
    std::vector<std::vector<int>> adj4(V4);
    // Component 1 (C4)
    adj4[0].push_back(1); adj4[1].push_back(0);
    adj4[1].push_back(2); adj4[2].push_back(1);
    adj4[2].push_back(3); adj4[3].push_back(2);
    adj4[3].push_back(0); adj4[0].push_back(3);
    // Component 2 (C3) starting from vertex 5
    adj4[5].push_back(6); adj4[6].push_back(5);
    adj4[6].push_back(7); adj4[7].push_back(6);
    adj4[7].push_back(5); adj4[5].push_back(7);


    std::cout << "Example 4 (Disconnected, C4 + C3): " << (checkBipartite(V4, adj4) ? "Is Bipartite" : "Not Bipartite") << std::endl; // Expected: Not Bipartite

    return 0;
}

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

// Hàm kiểm tra tính hai phía sử dụng DFS cho một thành phần liên thông
// u: đỉnh hiện tại
// c: màu cần tô cho đỉnh u (0 hoặc 1)
bool isBipartiteDFS(int u, int c, const std::vector<std::vector<int>>& adj, std::vector<int>& color) {
    color[u] = c; // Tô màu đỉnh u

    // Duyệt qua tất cả hàng xóm của đỉnh u
    for (int v : adj[u]) {
        // Nếu đỉnh v chưa được tô màu (-1)
        if (color[v] == -1) {
            // Gọi đệ quy DFS cho v với màu đối diện
            if (!isBipartiteDFS(v, 1 - c, adj, color)) {
                // Nếu lời gọi đệ quy phát hiện mâu thuẫn
                return false;
            }
        }
        // Nếu đỉnh v đã được tô màu và có CÙNG màu với u
        else if (color[v] == color[u]) {
            // Phát hiện mâu thuẫn, đồ thị không phải hai phía
            return false;
        }
    }

    // Nếu duyệt xong các hàng xóm mà không có mâu thuẫn
    return true;
}

// Hàm chính kiểm tra đồ thị hai phía (xử lý cả đồ thị không liên thông)
bool checkBipartiteDFS(int V, const std::vector<std::vector<int>>& adj) {
    // Mảng color để lưu màu của các đỉnh. -1: chưa tô màu, 0: màu 0, 1: màu 1
    std::vector<int> color(V, -1);

    // Duyệt qua tất cả các đỉnh để xử lý các thành phần liên thông
    for (int i = 0; i < V; ++i) {
        // Nếu đỉnh i chưa được tô màu, bắt đầu DFS từ đỉnh này
        if (color[i] == -1) {
            // Bắt đầu DFS với màu 0 cho đỉnh i
            if (!isBipartiteDFS(i, 0, adj, color)) {
                // Nếu một thành phần liên thông bất kỳ không phải hai phía
                return false;
            }
        }
    }

    // Nếu tất cả các thành phần liên thông đều là hai phía
    return true;
}

int main() {
    // Ví dụ 1: Đồ thị hai phía (chu trình C4)
    // 0 -- 1
    // |    |
    // 3 -- 2
    int V1 = 4;
    std::vector<std::vector<int>> adj1(V1);
    adj1[0].push_back(1); adj1[1].push_back(0);
    adj1[1].push_back(2); adj1[2].push_back(1);
    adj1[2].push_back(3); adj1[3].push_back(2);
    adj1[3].push_back(0); adj1[0].push_back(3);

    std::cout << "Example 1 (C4) using DFS: " << (checkBipartiteDFS(V1, adj1) ? "Is Bipartite" : "Not Bipartite") << std::endl; // Expected: Is Bipartite

    // Ví dụ 2: Đồ thị không hai phía (chu trình C3)
    // 0 -- 1
    // |  /
    // | /
    // 2
    int V2 = 3;
    std::vector<std::vector<int>> adj2(V2);
    adj2[0].push_back(1); adj2[1].push_back(0);
    adj2[1].push_back(2); adj2[2].push_back(1);
    adj2[2].push_back(0); adj2[0].push_back(2);

    std::cout << "Example 2 (C3) using DFS: " << (checkBipartiteDFS(V2, adj2) ? "Is Bipartite" : "Not Bipartite") << std::endl; // Expected: Not Bipartite

    // Ví dụ 3: Đồ thị không liên thông, cả hai thành phần đều là hai phía
    // 0 -- 1      2 -- 3
    // |    |      |    |
    // 4 -- 5      6 -- 7
    int V3 = 8;
    std::vector<std::vector<int>> adj3(V3);
    // Component 1 (C4)
    adj3[0].push_back(1); adj3[1].push_back(0);
    adj3[1].push_back(5); adj3[5].push_back(1);
    adj3[5].push_back(4); adj3[4].push_back(5);
    adj3[4].push_back(0); adj3[0].push_back(4);
    // Component 2 (C4)
    adj3[2].push_back(3); adj3[3].push_back(2);
    adj3[3].push_back(7); adj3[7].push_back(3);
    adj3[7].push_back(6); adj3[6].push_back(7);
    adj3[6].push_back(2); adj3[2].push_back(6);

    std::cout << "Example 3 (Disconnected) using DFS: " << (checkBipartiteDFS(V3, adj3) ? "Is Bipartite" : "Not Bipartite") << std::endl; // Expected: Is Bipartite

    // Ví dụ 4: Đồ thị không liên thông, một thành phần là hai phía, một không
    // 0 -- 1     5 -- 6
    // |    |     |  /
    // 3 -- 2     7
    int V4 = 8;
    std::vector<std::vector<int>> adj4(V4);
    // Component 1 (C4)
    adj4[0].push_back(1); adj4[1].push_back(0);
    adj4[1].push_back(2); adj4[2].push_back(1);
    adj4[2].push_back(3); adj4[3].push_back(2);
    adj4[3].push_back(0); adj4[0].push_back(3);
    // Component 2 (C3) starting from vertex 5
    adj4[5].push_back(6); adj4[6].push_back(5);
    adj4[6].push_back(7); adj4[7].push_back(6);
    adj4[7].push_back(5); adj4[5].push_back(7);

    std::cout << "Example 4 (Disconnected, C4 + C3) using DFS: " << (checkBipartiteDFS(V4, adj4) ? "Is Bipartite" : "Not Bipartite") << std::endl; // Expected: Not Bipartite


    return 0;
}

// Hướng dẫn giải bài "Hòn đảo cô đơn"

// 1. Biểu diễn đồ thị:
//    - Sử dụng danh sách kề (adjacency list) để lưu trữ các cây cầu một chiều.
//      Ví dụ: vector<vector<int>> adj; adj[u] chứa danh sách các đảo v có cầu u -> v.
//    - Cần lưu trữ bậc ra (out-degree) của mỗi đảo, vì xác suất di chuyển từ đảo u đến mỗi đảo lân cận v là 1 / out_degree[u].
//      Ví dụ: vector<int> out_degree; out_degree[u] là số lượng đảo có thể đi trực tiếp từ u.

// 2. Tính toán xác suất:
//    - Bài toán yêu cầu tìm xác suất bị kẹt lại tại mỗi đảo (có bậc ra bằng 0).
//    - Xác suất này là tổng xác suất của tất cả các con đường từ đảo xuất phát S đến đảo đó.
//    - Vì có thể có chu trình trong đồ thị (mặc dù một lần đi không quay lại đảo đã thăm), xác suất dòng chảy có thể phức tạp. Tuy nhiên, quy tắc "không thể di chuyển tiếp" khi bậc ra bằng 0 đảm bảo rằng mọi luồng xác suất cuối cùng đều hội tụ về các đảo có bậc ra 0.
//    - Ta có thể mô phỏng quá trình lan truyền xác suất theo từng bước (từng "đợt" di chuyển).
//    - Khởi tạo: Đảo S có xác suất 1.0 để bắt đầu tại đó. Các đảo khác có xác suất 0.0.
//    - Lặp lại nhiều lần (số bước đủ lớn để xác suất hội tụ):
//        - Tại mỗi bước, xác suất hiện có tại một đảo u sẽ được phân tán đều cho các đảo lân cận nếu out_degree[u] > 0.
//        - Nếu out_degree[u] == 0, xác suất hiện có tại u sẽ "bị kẹt" tại u và không được phân tán tiếp. Xác suất này cộng dồn vào tổng xác suất bị kẹt tại u.
//        - Sử dụng hai mảng xác suất: `current_prob` (xác suất đến đảo ở bước hiện tại) và `next_prob` (xác suất đến đảo ở bước tiếp theo).
//        - Sử dụng một mảng `total_stuck_prob` để cộng dồn xác suất bị kẹt tại các đảo có out_degree == 0.

// 3. Chi tiết thuật toán lan truyền xác suất:
//    - Khởi tạo `current_prob[1...N]` = 0.0, `current_prob[S]` = 1.0.
//    - Khởi tạo `total_stuck_prob[1...N]` = 0.0.
//    - Lặp lại khoảng 1000 đến 2000 lần (số lần lặp đủ lớn cho N=100, đảm bảo xác suất nhỏ hội tụ hoặc trở nên không đáng kể):
//        - Khởi tạo `next_prob[1...N]` = 0.0.
//        - Duyệt qua tất cả các đảo u từ 1 đến N:
//            - Nếu `current_prob[u]` nhỏ (ví dụ: < 1e-15), bỏ qua để tránh lan truyền nhiễu số thực.
//            - Nếu `out_degree[u] == 0`:
//                - Cộng `current_prob[u]` vào `total_stuck_prob[u]`.
//            - Ngược lại (`out_degree[u] > 0`):
//                - Tính xác suất truyền cho mỗi đảo lân cận: `p_transfer = current_prob[u] / out_degree[u]`.
//                - Duyệt qua tất cả các đảo lân cận v của u (adj[u]):
//                    - Cộng `p_transfer` vào `next_prob[v]`.
//        - Gán `current_prob = next_prob` cho lần lặp tiếp theo.

// 4. Tìm kết quả:
//    - Sau khi kết thúc các bước lặp, mảng `total_stuck_prob` sẽ chứa xác suất (đã hội tụ) bị kẹt tại mỗi đảo có out_degree == 0. Các đảo có out_degree > 0 sẽ có `total_stuck_prob` bằng 0.
//    - Tìm xác suất tối đa `max_prob` trong mảng `total_stuck_prob` (chỉ xét các đảo có out_degree == 0).
//    - Thu thập tất cả các chỉ số đảo i mà `out_degree[i] == 0` và `total_stuck_prob[i]` rất gần với `max_prob` (sử dụng sai số 10^-6: `fabs(total_stuck_prob[i] - max_prob) < 1e-6`).
//    - Sắp xếp các chỉ số đảo đã thu thập theo thứ tự tăng dần.
//    - In ra các chỉ số đảo đó, cách nhau bởi dấu cách.

// 5. Lưu ý:
//    - Sử dụng kiểu dữ liệu `double` cho xác suất.
//    - Cần cẩn thận với chỉ số đảo (1-based vs 0-based). Nếu dùng 0-based trong code, nhớ điều chỉnh khi đọc S và in kết quả.
//    - Số lần lặp đủ lớn là quan trọng để xác suất hội tụ, đặc biệt trong các đồ thị có chu trình. 1000-2000 thường đủ cho N=100.