cpp-045Bước 1Nâng cao
Giải bài toán 2-SAT bằng thuật toán Tarjan thành phần liên thông mạnh
Cho hệ ràng buộc gồm N biến mệnh đề x1, x2, …, xN và M mệnh đề dạng (u ∨ v), trong đó u và v là các biến hoặc phủ định của biến:
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Đồ thị & Giải thuật đồ thị trong C++
Mô hình hóa các mạng lưới phức tạp bằng đồ thị. Cài đặt các thuật toán tìm đường, liên thông và tối ưu mạng lưới với hiệu năng cực cao bằng C++ STL.
29
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
0
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
0
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
29
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Lưu trữ đồ thị
Biểu diễn danh sách kề bằng vector<pair<int, int>> adj[N].
Bước 2
Duyệt BFS & DFS
Duyệt đồ thị, đếm thành phần liên thông, tô màu đồ thị và tìm kiếm đường đi.
Bước 3
Thuật toán Dijkstra
Tìm đường đi ngắn nhất đồ thị có trọng số không âm dùng std::priority_queue trong O(E log V).
Bước 4
Cây khung nhỏ nhất (MST)
Thuật toán Kruskal kết hợp cấu trúc dữ liệu Disjoint Set Union (DSU).
Lỗi thường gặp & Cách phòng tránh
•
Dùng queue thường cho Dijkstra thay vì priority_queue dẫn đến độ phức tạp thời gian tăng vọt.
•
Không khởi tạo khoảng cách ban đầu bằng vô cùng cực lớn (0x3f3f3f3f hoặc 1e18 cho long long).
Danh sách bài tập thực hành (29 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Nâng cao 29 bài
Thử thách
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
cpp-105Bước 2Nâng cao
Co đồ thị SCC và Đường đi dài nhất trên đồ thị rút gọn DAG
Cho một đồ thị có hướng gồm N đỉnh và M cạnh. Mỗi đỉnh u có chứa một lượng tài nguyên là số nguyên Vu. Khi bạn đi qua một đỉnh, bạn có thể thu thập toàn bộ tài nguyên tại đỉnh đó…
cpp-176Bước 3Nâng cao
Cây khung nhỏ nhất có hướng (Thuật toán Chu-Liu/Edmonds)
Cho đồ thị có hướng gồm N đỉnh (được đánh số từ 0 đến N-1) và M cạnh có trọng số không âm. Cho một đỉnh gốc R.
cpp-161Bước 4Nâng cao
Sắp Xếp Tô-pô - Từ Điển Tiếng Ngoài Hành Tinh (Alien Dictionary)
Trong một ngôn ngữ ngoài hành tinh bí ẩn, người ta sử dụng các chữ cái tiếng Anh in thường nhưng theo một thứ tự bảng chữ cái hoàn toàn khác.
cpp-093Bước 5Nâng cao
Biến đổi từ vựng Word Ladder: BFS hai đầu (Bidirectional BFS)
Cho từ bắt đầu start, từ đích target và một tập từ điển gồm N từ có cùng độ dài L. Mỗi bước biến đổi chỉ được phép thay đổi đúng 1 ký tự và từ mới tạo thành phải nằm trong tập từ đ…
cpp-100Bước 6Nâng cao
Từ điển người ngoài hành tinh: Sắp xếp Tô-pô trên đồ thị ký tự
Cho danh sách N từ đã được sắp xếp theo thứ tự từ điển của một ngôn ngữ mới. Bảng chữ cái của ngôn ngữ này gồm các chữ cái tiếng Anh in thường ('a' đến 'z'). Hãy xác định thứ tự củ…
cpp-163Bước 7Nâng cao
Dijkstra Trên Đồ Thị Trạng Thái - Tối Đa K Vé Giảm Giá 50%
Có N thành phố và M chuyến bay một chiều. Chuyến bay từ u đến v có giá vé nguyên là w.
cpp-164Bước 8Nâng cao
Chu Trình và Đường Đi Euler Trên Đồ Thị Có Hướng (Hierholzer Algorithm)
Cho một đồ thị có hướng gồm N đỉnh và M cung.
cpp-165Bước 9Nâng cao
Thành Phần Liên Thông 2-Cạnh (2-Edge-Connected Components)
Cho một đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh. Đồ thị có thể không liên thông.
cpp-177Bước 10Nâng cao
Thuật toán Boruvka tìm cây khung nhỏ nhất
Cho đồ thị vô hướng liên thông gồm N đỉnh (đánh số 0 đến N-1) và M cạnh có trọng số.
Chuyên sâu
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
cpp-166Bước 11Nâng cao
Thành Phần Liên Thông 2-Đỉnh (Block-Cut Tree)
Cho một đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh.
cpp-178Bước 12Nâng cao
Đếm tam giác và chu trình độ dài 4 trong đồ thị
Cho đơn đồ thị vô hướng gồm N đỉnh (đánh số 0 đến N-1) và M cạnh. Đồ thị không có khuyên hay cạnh lặp.
cpp-104Bước 13Nâng cao
Cây thống trị Dominator Tree: Thuật toán Lengauer-Tarjan
Cho một đồ thị có hướng gồm N đỉnh và M cạnh. Đỉnh nguồn xuất phát là đỉnh 1 (mọi đỉnh khác đều tới được từ đỉnh 1). Hãy tìm nút thống trị trực tiếp idom(u) của tất cả các đỉnh u t…
cpp-204Bước 14Nâng cao
Chuyển Đổi Danh Sách Cạnh Sang Danh Sách Kề Đồ Thị
Trong lý thuyết đồ thị và giải thuật, danh sách kề (Adjacency List) là cách biểu diễn đồ thị phổ biến nhất nhờ tính tối ưu bộ nhớ O(V + E) và khả năng duyệt các đỉnh láng giềng nha…
cpp-162Bước 15Nâng cao
Đường Đi Ngắn Nhất Bằng Thuật Toán 0-1 BFS (0-1 BFS via Deque)
Cho một đồ thị có hướng gồm N đỉnh (đánh số từ 1 đến N) và M cung. Trọng số của mỗi cung chỉ có thể nhận một trong hai giá trị là 0 hoặc 1.
cpp-017Bước 16Nâng cao
Duyệt đồ thị BFS tìm đường đi ngắn nhất không trọng số
Mạng lưới máy chủ của AI Empire Academy gồm V máy chủ được đánh số từ 1 đến V và E kênh truyền thông hai chiều nối giữa các máy chủ (1 ≤ V ≤ 105, 0 ≤ E ≤ 2 · 105). Mỗ…
cpp-018Bước 17Nâng cao
Đếm số thành phần liên thông và tìm cụm máy chủ lớn nhất bằng DFS
Hạ tầng tính toán đám mây của AI Empire Academy có N máy chủ được đánh số từ 1 đến N và M kết nối mạng nội bộ hai chiều (1 ≤ N ≤ 105, 0 ≤ M ≤ 2 · 105).
cpp-020Bước 18Nâng cao
Cây khung nhỏ nhất bằng thuật toán Kruskal và DSU
AI Empire Academy cần lắp đặt hệ thống cáp mạng quang tốc độ cao kết nối N trạm nghiên cứu trí tuệ nhân tạo (1 ≤ N ≤ 105). Có M tuyến cáp tiềm năng hai chiều có thể lắp đặt (0…
cpp-025Bước 19Nâng cao
Sắp xếp Tô-pô bằng thuật toán Kahn và phát hiện chu trình
Hệ thống xử lý phân tán của AI Empire Academy cần lập lịch thực thi N tác vụ được đánh số từ 1 đến N (1 ≤ N ≤ 105). Có M ràng buộc phụ thuộc (0 ≤ M ≤ 2 · 105), mỗi rà…
cpp-026Bước 20Nâng cao
Thuật toán Floyd-Warshall tìm đường đi ngắn nhất giữa mọi cặp đỉnh
Hệ thống mạng lưới máy chủ vùng của AI Empire Academy gồm N trạm trung chuyển dữ liệu được đánh số từ 1 đến N (1 ≤ N ≤ 400) và M kênh kết nối một chiều (0 ≤ M ≤ 2 · 10…
Tối ưu & chứng minh
Ràng buộc chặt về thời gian và bộ nhớ — mức thi đấu.
cpp-019Bước 21Nâng cao
Thuật toán Dijkstra tìm đường đi ngắn nhất có trọng số
Hệ thống mạng lưới truyền tải mô hình trọng số lớn của AI Empire Academy gồm V trung tâm dữ liệu đánh số từ 1 đến V và E tuyến cáp quang một chiều (1 ≤ V ≤ 105, 0 ≤ E ≤ 2…
cpp-046Bước 22Nâng cao
Thuật toán Kosaraju tìm thành phần liên thông mạnh (SCC)
Cho một đồ thị có hướng gồm N đỉnh (1 ≤ N ≤ 105) và M cạnh (0 ≤ M ≤ 2 · 105). Hãy đếm số lượng thành phần liên thông mạnh (SCC) của đồ thị.
cpp-048Bước 23Nâng cao
Thuật toán Bellman-Ford / SPFA tìm đường đi ngắn nhất và phát hiện chu trình âm
Cho một đồ thị có hướng gồm N đỉnh (1 ≤ N ≤ 2500) và M cạnh (1 ≤ M ≤ 5000). Mỗi cạnh có trọng số w (có thể âm).
cpp-058Bước 24Nâng cao
Bellman-Ford: Truy vết Chu trình Âm
Cho một đồ thị có hướng gồm N đỉnh và M cạnh có trọng số (trọng số có thể âm). Hãy kiểm tra xem đồ thị có chứa chu trình trọng số âm hay không. Nếu có, hãy tìm và in ra các đỉnh th…
cpp-036Bước 25Nâng cao
Thuật toán Tarjan tìm khớp và cầu trên đồ thị vô hướng
Hạ tầng mạng viễn thông của AI Empire Academy gồm N trạm máy chủ (1 ≤ N ≤ 105) và M đường cáp quang nối trực tiếp (1 ≤ M ≤ 2 · 105). Đồ thị là vô hướng, có thể không…
cpp-037Bước 26Nâng cao
Chu trình Euler và thuật toán Hierholzer trên đồ thị có hướng
Hệ thống mạng máy chủ của AI Empire Academy gồm N trạm máy chủ (1 ≤ N ≤ 105) và M tuyến cáp quang một chiều (1 ≤ M ≤ 2 · 105). Đồ thị có thể có đa cạnh.
cpp-059Bước 27Nâng cao
Block-Cut Tree: Thành phần Song liên thông Đỉnh
Cho một đồ thị vô hướng liên thông gồm N đỉnh và M cạnh. Xây dựng Block-Cut Tree của đồ thị và đếm số lượng khối (Biconnected Components / Blocks) cùng số lượng đỉnh khớp (articula…
cpp-116Bước 28Nâng cao
Giao Hai Matroid - Rừng Cây Đa Sắc Cực Đại (Colorful Forest)
Cho một đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh. Mỗi cạnh ei = (ui, vi) được tô một màu nguyên dương ci.
cpp-120Bước 29Nâng cao
Cây Có Hướng Tối Tiểu (Directed MST) - Thuật Toán Edmonds' Chu-Liu
Cho một đồ thị có hướng G = (V, E) gồm N đỉnh (đánh số 1 … N) và M cung có trọng số. Cho trước một đỉnh gốc R.