Bài 32.4. Mạng lưới Truyền tải Dữ liệu Vòng lặp Tự Phục hồi - [Độ khó: Khó]

Trong một hệ thống mạng lưới dạng vòng lặp (ring network) khẩn cấp, mỗi nút (node) là một trạm truyền tải dữ liệu. Dữ liệu có thể được truyền tải theo cả hai chiều (thuận và ngược chiều kim đồng hồ) giữa các trạm liền kề. Hệ thống này cần phải có khả năng tự phục hồi khi một trạm bị lỗi hoặc một trạm mới được thêm vào. Đồng thời, để tối ưu hóa hiệu suất, hệ thống cần tính toán "khoảng cách" hiệu quả nhất (số lượng trạm cần đi qua) giữa hai trạm bất kỳ trong vòng lặp hiện tại.

Bạn được yêu cầu xây dựng một mô hình cho mạng lưới này sử dụng Danh sách liên kết đôi-vòng (Doubly Circular Linked List).

INPUT FORMAT

Dòng đầu tiên là một số nguyên N (1 <= N <= 10000), số lượng thao tác. Tiếp theo là N dòng, mỗi dòng mô tả một thao tác:

• ADD <station_ID> <neighbor_ID>: Thêm một trạm mới station_ID vào mạng lưới. Trạm mới này sẽ được đặt ngay sau neighbor_ID (theo chiều thuận). neighbor_ID phải tồn tại trong mạng lưới. Nếu mạng rỗng, station_ID trở thành trạm đầu tiên.
• REMOVE <station_ID>: Loại bỏ trạm station_ID khỏi mạng lưới. Các trạm lân cận sẽ tự động nối lại.
• GET_DISTANCE <station_A_ID> <station_B_ID>: Tính toán khoảng cách ngắn nhất (số lượng trạm cần đi qua, không tính trạm xuất phát nhưng tính trạm đích) giữa station_A_ID và station_B_ID. Khoảng cách có thể là 0 nếu A và B là cùng một trạm.
• PRINT_NETWORK: In ra tất cả các station_ID theo thứ tự thuận chiều kim đồng hồ, bắt đầu từ trạm đầu tiên được thêm vào (hoặc trạm còn lại nếu các trạm đầu tiên đã bị xóa).

Tất cả các station_ID là số nguyên dương duy nhất (1 <= station_ID <= 10^9). Các thao tác ADD đảm bảo station_ID chưa tồn tại và neighbor_ID tồn tại (trừ khi mạng rỗng). Các thao tác REMOVE và GET_DISTANCE đảm bảo các station_ID được nhắc đến đều tồn tại trong mạng lưới.

OUTPUT FORMAT

Với mỗi thao tác GET_DISTANCE, in ra khoảng cách ngắn nhất. Với mỗi thao tác PRINT_NETWORK:

• Nếu mạng rỗng, in ra "Empty".
• Ngược lại, in ra các station_ID cách nhau bởi dấu cách, theo thứ tự tuần hoàn.

Ví dụ:

Input:

7
ADD 10 -1
ADD 20 10
ADD 30 20
PRINT_NETWORK
GET_DISTANCE 10 30
REMOVE 20
GET_DISTANCE 10 30
PRINT_NETWORK

Output:

10 20 30
2
1
10 30

Giải thích:

• ADD 10 -1: Thêm 10. Mạng: 10.
• ADD 20 10: Thêm 20 sau 10. Mạng: 10 <-> 20.
• ADD 30 20: Thêm 30 sau 20. Mạng: 10 <-> 20 <-> 30.
• PRINT_NETWORK: In ra 10 20 30.
• GET_DISTANCE 10 30:
  • Chiều thuận (10 -> 20 -> 30): đi qua 2 trạm (20, 30) -> khoảng cách 2.
  • Chiều ngược (10 -> 30): đi qua 1 trạm (30) -> khoảng cách 1.
  • Khoảng cách ngắn nhất là 1. Lưu ý: Ví dụ output là 2. Let's re-evaluate "number of stations to pass through". If it's number of edges, then 10->20->30 is 2 edges. 10->30 is 1 edge. So the example output of 2 implies "shortest path in terms of nodes visited including destination but excluding source". If 10->20->30, nodes are 10, 20, 30. Path length is 2. If 10->30, nodes are 10, 30. Path length is 1. The definition "số lượng trạm cần đi qua, không tính trạm xuất phát nhưng tính trạm đích" implies 10->20->30, the path is 20, 30 (2 stations). 10->30, path is 30 (1 station). So the correct answer for 10-30 in 10 20 30 should be 1 (clockwise) or 2 (counter-clockwise through 20). Shortest is 1.
  • Correction needed: The example says 2. This definition is tricky. Let's assume "shortest path" means number of "hops" (edges).
    • From 10 to 30:
      • Clockwise: 10 -> 20 (1 hop) -> 30 (2 hops). Distance = 2.
      • Counter-clockwise: 10 -> 30 (1 hop). Distance = 1.
    • So the shortest should be 1. The example output is 2. This implies my understanding of "shortest distance" might be different from what the problem intended in the example.
    • Let's re-read: "số lượng trạm cần đi qua, không tính trạm xuất phát nhưng tính trạm đích".
      • Path 10 -> 20 -> 30. Trạm đi qua: 20, 30 (2 trạm).
      • Path 10 -> 30. Trạm đi qua: 30 (1 trạm).
    • Ah, maybe the example expects the maximum of the two directions, or implies a non-standard "shortest path". Given the problem is "Khó", it should be the standard "shortest path" = minimum hops.
    • Let's correct the example output for 10-30 after removing 20:
      • After removing 20, network is 10 <-> 30.
      • From 10 to 30:
        • Clockwise: 10 -> 30 (1 hop).
        • Counter-clockwise: 10 -> 30 (1 hop).
      • Shortest is 1.
    • The example output for GET_DISTANCE 10 30 is 2 for 10 20 30 network. This is confusing. Maybe it expects a specific direction, or total path length? No, "shortest path" usually means minimum.
    • Let's assume the example is for a "bad" calculation or the definition of "distance" is tricky.
    • If 10 20 30 is the network, and you want GET_DISTANCE 10 30.
      • 10 -> 20 -> 30 (2 hops)
      • 10 -> 30 (1 hop)
    • Shortest is 1. If output is 2, it's problematic.
    • What if the problem wants "longest path" or something strange? No, it says "ngắn nhất".
    • The only way to get 2 for GET_DISTANCE 10 30 is if it counts the number of nodes in the path (excluding source), not hops.
      • Path 1: 10 -> 20 -> 30. Nodes passed: 20, 30 (2 nodes).
      • Path 2: 10 -> 30. Nodes passed: 30 (1 node).
      • Shortest of these is 1.
    • This example output is definitely wrong for a standard "shortest path" or my interpretation.
    • Let's change the example to be consistent with standard shortest path (minimum hops).

Revised Example for 32.4 (Corrected GET_DISTANCE interpretation): Input:

7
ADD 10 -1
ADD 20 10
ADD 30 20
PRINT_NETWORK
GET_DISTANCE 10 30
REMOVE 20
GET_DISTANCE 10 30
PRINT_NETWORK

Output:

10 20 30
1
1
10 30

Giải thích:

• ADD 10 -1: Thêm 10. Mạng: 10.
• ADD 20 10: Thêm 20 sau 10. Mạng: 10 <-> 20.
• ADD 30 20: Thêm 30 sau 20. Mạng: 10 <-> 20 <-> 30.
• PRINT_NETWORK: In ra 10 20 30.
• GET_DISTANCE 10 30:
  • Từ 10 đến 30:
    • Theo chiều thuận (10 -> 20 -> 30): đi qua 2 trạm (20, 30). Khoảng cách là 2.
    • Theo chiều ngược (10 -> 30): đi qua 1 trạm (30). Khoảng cách là 1.
  • Khoảng cách ngắn nhất là 1.
• REMOVE 20: Loại bỏ trạm 20. Mạng: 10 <-> 30.
• GET_DISTANCE 10 30:
  • Từ 10 đến 30:
    • Theo chiều thuận (10 -> 30): đi qua 1 trạm (30). Khoảng cách là 1.
    • Theo chiều ngược (10 -> 30): đi qua 1 trạm (30). Khoảng cách là 1.
  • Khoảng cách ngắn nhất là 1.
• PRINT_NETWORK: In ra 10 30.

This revised example aligns with a standard "shortest path" (minimum number of intermediate nodes/hops) interpretation.