Thành phố Cuồng loạn

Giới thiệu Đồ thị song liên thông điểm (biconnected graph) và đồ thị song liên thông cạnh (edge-biconnected graph) là hai khái niệm quan trọng trong lý thuyết đồ thị. Một đồ thị được gọi là song liên thông điểm nếu việc loại bỏ bất kỳ một đỉnh nào (không phải hai đỉnh đang xét) không làm thay đổi tính liên thông của đồ thị. Tương tự, một đồ ...

Dưới đây là phân tích và giải pháp cho một số bài toán tiêu biểu từ kỳ thi Newcoder Multi-School 6 (2024), tập trung vào các kỹ thuật thuật toán chính. Bài toán A: Cake Ý tưởng giải Đây là một bài toán kết hợp lý thuyết trò chơi đơn giản và quy hoạch động trên cây. Mục tiêu của hai người chơi được định nghĩa rõ ràng: Oscar sẽ cắt bánh để đạt đ ...

Nền tảng và Khái niệm Cơ bản Để hiểu sâu về thuật toán Tarjan, chúng ta cần nắm vững cấu trúc của cây tìm kiếm (DFS Tree) trên đồ thị. Cần phân biệt rõ ràng giữa đồ thị gốc và cây sinh ra từ quá trình duyệt DFS. Hai mảng quan trọng nhất trong quá trình thực thi là: disc[u]: Lưu trữ thời điểm lần đầu tiên truy cập vào đỉnh u. low[u]: Giá trị ...