Bộ chọn chiến lược đồ thị

Bối cảnh và bài toán

Trước khi viết code, nhóm kỹ thuật cần chọn một thuật toán đã học trong các buổi B25–B28. Mỗi tình huống mô tả mục tiêu và đặc điểm cạnh. Không được chỉ nhìn thấy đồ thị có hướng/vô hướng rồi đoán DFS hay BFS.

Yêu cầu

Với mỗi tình huống, in một trong năm nhãn: DFS, BFS, TOPO, DIJKSTRA, CHUA_HOC.

• task=1: kiểm tra khả năng đi tới một đỉnh (reachability), chọn DFS.
• task=2: tìm đường đi ngắn nhất. Nếu mọi cạnh có chi phí 1 (weighted=0), chọn BFS. Nếu có trọng số không âm (weighted=1, negative=0), chọn DIJKSTRA. Nếu có cạnh âm (weighted=1, negative=1), in CHUA_HOC: B29 chưa học thuật toán xử lý trường hợp này.
• task=3: tìm thứ tự phụ thuộc trên DAG (đề bảo đảm không chu trình), chọn TOPO.

Hai cờ weighted và negative không ảnh hưởng khi task=1 hoặc task=3. Dữ liệu luôn có negative=0 khi weighted=0.

Input

Dòng đầu chứa số nguyên T. Mỗi trong T dòng tiếp theo có ba số nguyên task weighted negative.

Output

In T dòng, mỗi dòng chứa đúng một nhãn thuật toán.

Ràng buộc

• 1 <= T <= 10^5.
• 1 <= task <= 3; weighted,negative thuộc {0,1}.
• Nếu weighted=0 thì negative=0.

Chấm điểm

Ví dụ 1

Input

5
1 0 0
2 0 0
3 0 0
2 1 0
2 1 1

Output

DFS
BFS
TOPO
DIJKSTRA
CHUA_HOC

Giải thích. Mục tiêu cần được nhận diện trước: khả năng đi tới → DFS; đường ngắn nhất không trọng số → BFS; thứ tự DAG → Topo; đường ngắn nhất trọng số không âm → Dijkstra. Trường hợp cạnh âm cần kiến thức của buổi sau nên chưa chọn thuật toán đó ở B29.

Ví dụ 2

Input

3
3 1 1
1 1 0
2 1 0

Output

TOPO
DFS
DIJKSTRA

Giải thích. Với bài toán topo chỉ cần đồ thị là DAG; với reachability, dấu trọng số không ảnh hưởng; với shortest path trọng số không âm, chọn Dijkstra.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated; thiết kế theo phạm vi lựa chọn giải thuật của B29.