Đồ thị / Logic

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 1)

Đồ thị / Logic

2-Satisfiability (2-SAT)

Thời gian (Time) O(V + E)
Không gian (Space) O(V + E)

Mô tả nguyên lý

Giải bài toán thỏa mãn mệnh đề dạng (A v B) với các biến logic boolean.

Cài đặt mẫu (Implementation)

// Xây dựng đồ thị hàm ý (implication graph) và kiểm tra các biến có cùng thành phần liên thông mạnh với phủ định của nó hay không qua Tarjan.