Hướng giải của Tô màu đồ thị ba màu dùng 2-SAT

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải

Phân tích

Mỗi đỉnh \(i\) chỉ được chọn giữa hai màu \((c_1, c_2)\). Dùng biến boolean \(x_i\):

  • \(x_i = 0\): chọn màu \(c_1\)
  • \(x_i = 1\): chọn màu \(c_2\)

Với mỗi cạnh \((u, v)\), hai đỉnh không được cùng màu. Xét từng tổ hợp giá trị của \((x_u, x_v)\):

  • Nếu màu của \(u\) (ứng với \(x_u = val_u\)) bằng màu của \(v\) (ứng với \(x_v = val_v\)), ta cấm tổ hợp đó bằng mệnh đề 2-SAT.

Cụ thể, với bốn tổ hợp \((0,0), (0,1), (1,0), (1,1)\), kiểm tra từng tổ hợp. Nếu hai màu trùng nhau, thêm mệnh đề cấm tổ hợp đó:

  • Tổ hợp \((0,0)\): thêm \((\neg x_u \lor \neg x_v)\).
  • Tổ hợp \((0,1)\): thêm \((\neg x_u \lor x_v)\).
  • Tổ hợp \((1,0)\): thêm \((x_u \lor \neg x_v)\).
  • Tổ hợp \((1,1)\): thêm \((x_u \lor x_v)\).

Sau đó giải 2-SAT. Độ phức tạp: \(O(N + M)\).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> col1(n + 1), col2(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!(cin >> col1[i] >> col2[i])) return 0;
    }
    int sz = 2 * n + 2;
    vector<vector<int>> adj(sz), radj(sz);
    auto add_impl = [&](int u, int v) {
        adj[u].push_back(v);
        radj[v].push_back(u);
    };
    auto add_clause = [&](int a, int b) {
        int na = a > 0 ? 2 * a + 1 : 2 * (-a);
        int nb = b > 0 ? 2 * b + 1 : 2 * (-b);
        int a_node = a > 0 ? 2 * a : 2 * (-a) + 1;
        int b_node = b > 0 ? 2 * b : 2 * (-b) + 1;
        add_impl(na, b_node);
        add_impl(nb, a_node);
    };
    for (int i = 0; i < m; i++) {
        int u, v;
        if (!(cin >> u >> v)) return 0;
        int u0 = col1[u], u1 = col2[u];
        int v0 = col1[v], v1 = col2[v];
        if (u0 == v0) add_clause(-u, -v);
        if (u0 == v1) add_clause(-u, v);
        if (u1 == v0) add_clause(u, -v);
        if (u1 == v1) add_clause(u, v);
    }
    vector<int> order, comp(sz, 0);
    vector<bool> visited(sz, false);
    function<void(int)> dfs1 = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) if (!visited[v]) dfs1(v);
        order.push_back(u);
    };
    for (int i = 2; i <= 2 * n + 1; i++) if (!visited[i]) dfs1(i);
    int comp_id = 0;
    function<void(int)> dfs2 = [&](int u) {
        comp[u] = comp_id;
        for (int v : radj[u]) if (!comp[v]) dfs2(v);
    };
    for (int i = sz - 1; i >= 2; i--) {
        int u = order[i];
        if (!comp[u]) { comp_id++; dfs2(u); }
    }
    for (int i = 1; i <= n; i++) {
        if (comp[2 * i] == comp[2 * i + 1]) { cout << "NO\n"; return 0; }
    }
    cout << "YES\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.