Interesting Graph problem

Правка en1, от Gyanendu02, 2024-06-26 12:32:24

A system contains pods numbered from 1 to pods, distributed across multiple geographical regions. These pods are interconnected by n links, represented by the array connections, such that if two pods are connected directly or indirectly, they belong to the same region.

Each pod has a database connection to which it writes the critical data received. If a pod loses its database connection for some reason, it forwards the data to an active pod in the same region with the lowest ID, and that pod writes the data to the region's database. If there are no active pods left in the region, the data is not written, and an error is recorded in the logs.

Process q queries of two types: a data-sending query of the form "1 pod_id," or a database-connection-failure query of the form "2 pod_id."

For each data-sending query, the program should output the ID of the pod that writes the data to the database. Specifically, when a data-sending query is made to pod sender_pod_id, the program should find the active pod in the same region with the lowest ID and return its ID as the output. If there are no active pods in the region, the program should output -1.

Suppose pods = 3,n = 2 ,connections = [[1, 2], [2, 3]], q = 5, queries = [[2, 2], [1, 2], [2, 1], [2, 3], [1, 1]]. The output for this test case is [1, -1].

Теги dsa, graphs, dsu, dfs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Gyanendu02 2024-06-26 12:32:24 1354 Initial revision (published)