GATE CS 2025 Set 2 | Question 10

The diagram below shows a river system consisting of 7 segments, marked P, Q, R, S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, and Z5. We need to connect these zones using the least number of bridges. Out of the following options, which one is correct?

Note: The figure shown is representative.

A river map: segment P runs in from the left edge between Z2 (above) and Z1 (below) to a junction, where R rises to the top edge between Z2 and Z3 and Q continues right between Z3 and Z1. Q ends where S runs down to the bottom edge between Z1 and Z5 and T continues right between Z3 and Z5, and T then splits into V (between Z3 and Z4) and U (between Z4 and Z5).

Option A: Bridges on P, Q, and T
Option B: Bridges on P, Q, S, and T
Option C: Bridges on Q, R, T, and V (correct)
Option D: Bridges on P, Q, S, U, and V

Answer

(C)

Explanation

Treat each zone as a point and each river segment as a possible bridge between the two zones on its banks: P (Z1–Z2), R (Z2–Z3), Q (Z1–Z3), S (Z1–Z5), T (Z3–Z5), V (Z3–Z4) and U (Z4–Z5).

Joining 5 zones needs at least 4 bridges, and 4 are enough only if they reach every zone without forming a loop.

A has only 3 bridges and leaves Z4 cut off.
B also leaves Z4 cut off, and its bridges on Q, S and T join Z1, Z3 and Z5 in a loop.
C joins Z1, Z2, Z4 and Z5 each to Z3, so all zones are connected with 4 bridges.
D connects every zone but uses 5 bridges.

Answer: C