Skip to main content

Radio Stations

Challenge on lesson: Checkpoint — Graph Theory

CHALLENGE
Difficulty: intermediate+25 XP

**Description:** A network of n radio stations (1..n) and m two-way links. Broadcasts from station s reach every station in s's connected component. For each of q queries (a, b), answer whether a message can travel between a and b. **Input:** Line 1: n m q (1 <= n <= 100000, 0 <= m <= 200000, 1 <= q <= 100000). Next m lines: u v (links). Next q lines: a b (queries). **Output:** q lines, each YES if a and b are connected, otherwise NO. **Example:** 3 1 2 / 1 2 / 1 2 / 1 3 -> YES / NO.

Back to lesson: Checkpoint — Graph Theory