Dsa
Union Find
Hard
Optimal Network Path Management
You manage a series of connected servers in a data center and need to determine the optimal path to connect clients to servers with minimal disruption. Each connection can be disrupted and must be restored without creating cycles in the network. Given a list of connections and disruptions, determine if a connection can be restored without introducing a cycle.
Input Format:
- The first line contains an integer n (the number of servers) and an integer m (the number of connections).
- The next m lines each contain two integers, u and v, representing a connection between server u and server v.
- Then an integer d (the number of disruptions).
- The next d lines each contain two integers, x and y, representing a disruption between server x and server y.
Output Format:
- For each disruption, output 'RESTORE' if the connection can be restored without creating a cycle, and 'CYCLE' if it would create a cycle.
Example:
Input:
5 4
1 2
2 3
4 5
1 4
3
1 3
2 4
4 5
Output:
RESTORE
RESTORE
CYCLE
Key concepts
union_findnetworkpath_compression
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now