UVa 10687

From Algorithmist
Jump to navigation Jump to search

10687 - Monitoring the Amazon[edit]

Summary[edit]

Each vertex (station) is connected to two vertices - its two closest neighbors, with some tiebreaking rules. Construct the graph, and check if the resultant graph is connected.

Explanation[edit]

Construct the graph, and use any of the Graph Connectivity algorithms. Since V is at most 1000, implementation will do.

Gotcha's[edit]

  • Remember the tiebreaking rules:
    1. Choose the leftmost on the map (smallest x)
    2. Choose the southmost on the map (smallest y)

Implementations[edit]

Input[edit]

4
1 0 0 1 -1 0 0 -1
8
1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1 1 -1
6
0 3 0 4 1 3 -1 3 -1 -4 -2 -5
0

Output[edit]

All stations are reachable.
All stations are reachable.
There are stations that are unreachable.