Hauling Ore
Time limit1sMemory limit128 MB
For each queried mine in an undirected graph, print all mines at shortest distance exactly 2, in alphabetical order.
- Level
Medium5 of 10
- Topics
- Graph, BFS, Hash map, Implementation
- Solved
- No attempts yet
Problem
Administrator Selfridge is analyzing possible mining routes on Pandora. He has collected the connections between mines as a graph. The latest ore carriers can visit exactly 3 mining camps; in other words, starting from one mine they can reach any mine that is exactly 2 moves away.
For each queried mine, find every mine that can be reached with exactly 2 moves and no fewer — that is, every mine whose shortest number of moves from the given mine is exactly 2.
Connections between mines are bidirectional (the graph is undirected).
Input
The input consists of one or more independent problem instances.
Each instance begins with a line GRAPH BEGIN. The following lines list mines (nodes), each followed on the same line by its neighboring mines (edges): every such line starts with one mine's name and then lists the names of the mines it is connected to. A line GRAPH END ends the graph description.
After that, the mines to be analyzed are listed, one per line. Following this list of queries, a completely new problem instance may begin again from GRAPH BEGIN; each instance is independent and starts from scratch.
Some mines may appear only as neighboring mines, without being described on their own line. Mine names are arbitrary strings that contain no whitespace.
Output
For each queried mine, print one line. On that line, print the names of the mines that can be reached with exactly 2 moves and no fewer, in alphabetical order, each name followed by a single space. If there is no such mine, print an empty line.
Hint
