Duyệt đồ thị: BFS, DFS
40 bài duyệt đồ thị, độ khó tăng dần (rating 900 đến 2000): loang và thành phần liên thông, BFS đường đi ngắn nhất, BFS đa nguồn, BFS 0-1, BFS trên không gian trạng thái, đồ thị hai phía, phát hiện chu trình, sắp xếp topo, cầu, khớp và thành phần liên thông mạnh.
Đề bài
40
Mã
Tên
Nhóm
Độ khó
Điểm
% AC
# AC
cntrooms
Điểm1,00
Đếm Số Phòng
Loang (flood fill) đếm thành phần trên lưới
Chưa phân loại
Tỷ lệ AC
60,0%
AC
3
buildroads
Điểm1,00
Xây Đường
Đếm thành phần liên thông, nối thêm cạnh
Chưa phân loại
Tỷ lệ AC
80,0%
AC
3
msgroute
Điểm1,00
Đường Truyền Tin
BFS đường đi ngắn nhất, truy vết
Chưa phân loại
Tỷ lệ AC
85,7%
AC
5
piggyback
Điểm1,00
Cõng Bạn
Ba lần BFS, ghép khoảng cách tại điểm gặp
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
buildteams
Điểm1,00
Chia Đội
Kiểm tra đồ thị hai phía, tô hai màu
Chưa phân loại
Tỷ lệ AC
100,0%
AC
3
coursesched
Điểm1,00
Lịch Học
Sắp xếp topo (Kahn), phát hiện chu trình
Chưa phân loại
Tỷ lệ AC
71,4%
AC
3
flightrchk
Điểm1,00
Kiểm Tra Chuyến Bay
Liên thông mạnh: DFS trên đồ thị xuôi và ngược
Chưa phân loại
Tỷ lệ AC
100,0%
AC
2
gr03_lexpath
Điểm2,00
Đường đi ngắn nhất nhỏ nhất
BFS từ đích, đường ngắn nhất có thứ tự từ điển nhỏ nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
roundtrip
Điểm1,00
Vòng Tròn
DFS tìm chu trình trong đồ thị vô hướng
Chưa phân loại
Tỷ lệ AC
100,0%
AC
2
icpc25_mt_j
Điểm3,00
Mê cung sinh tồn
BFS trên trạng thái (ô, máu còn lại)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
monsters
Điểm1,00
Quái Vật
BFS đa nguồn quái vật rồi BFS người chơi
Chưa phân loại
Tỷ lệ AC
100,0%
AC
3
roundtrip2
Điểm1,00
Vòng Tròn II
DFS ba màu tìm chu trình có hướng
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
gr05_walls
Điểm3,00
Phá tường thoát ra
BFS 0-1: số tường ít nhất phải phá
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr05_jugs
Điểm3,00
Hai bình nước
BFS trên không gian trạng thái hai bình
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr09_lextopo
Điểm4,00
Thứ tự topo nhỏ nhất
Topo với hàng đợi ưu tiên, thứ tự nhỏ nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
planetkgd
Điểm1,00
Hành Tinh và Vương Quốc
Thành phần liên thông mạnh (Kosaraju/Tarjan)
Chưa phân loại
Tỷ lệ AC
100,0%
AC
2
conn2barn
Điểm1,00
Connecting Two Barns
Thành phần liên thông + hai con trỏ chọn cầu nối
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr05_keys
Điểm4,00
Chìa khóa và cửa
BFS trên (ô, tập chìa khóa bitmask)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gates
Điểm1,00
Xây cổng
Loang trên lưới phóng đại hai lần, đếm vùng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
mikemon
Điểm4,00
Khu rừng Biridian
BFS từ lối ra, so khoảng cách với đối thủ
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
ninjawall
Điểm4,00
Ninja và hẻm núi
BFS trạng thái (vách, độ cao) kèm mực nước
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
coursedep
Điểm4,00
Khóa học trực tuyến
DFS bao đóng phụ thuộc + topo, phát hiện chu trình
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
subway
Điểm5,00
Tàu điện ngầm
Tìm chu trình duy nhất rồi BFS đa nguồn
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
foxnames
Điểm5,00
Tên tác giả
Dựng đồ thị thứ tự chữ cái, sắp xếp topo
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gridmaze
Điểm5,00
Mê cung lưới
DFS giữ thành phần liên thông khi xóa k ô
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
voi15_reform
Điểm5,00
Kế hoạch cải tổ
Cầu + kích thước cây con DFS, đếm cách
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
nolongpath
Điểm5,00
Đồ thị không có đường đi dài
Tô hai màu để định hướng cạnh
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
robotrap
Điểm6,00
Kết quả trận đấu robot rap
Topo duy nhất + chặt nhị phân số trận
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
kcycle
Điểm6,00
Chu trình trong đồ thị
Cây DFS: cạnh ngược tạo chu trình dài
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr15_bridges
Điểm6,00
Dây cáp quan trọng
Tìm cầu (low-link) + kích thước cây con
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr15_cutvert
Điểm6,00
Đóng cửa thành phố
Khớp (articulation point), đếm thành phần
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr15_scc
Điểm6,00
Đường một chiều
Tarjan SCC, số cung tối thiểu để liên thông mạnh
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dirroads
Điểm6,00
Đảo chiều đường
Đồ thị hàm: tìm chu trình, đếm cách đảo chiều
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dream
Điểm1,00
Giấc mơ của Bessie
BFS trên trạng thái (ô, mùi, hướng trượt)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0