Đồ thị / Logic
2-Satisfiability (2-SAT)
ID: #103
Xem trên trang chủ
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.