DWITE, November 2011, Problem 5
Scientists have finally discovered a method of creating a portal between two places (on Earth, as apparently the physics gets tricky when we get to space). Before mass producing their device the scientists want you to create software that checks whether two places are connected via a series of their portals. Help them with this project (Note: Portals are bidirectional, so they can be travelled through in both directions).
The input will contain 5 test sets. The first line of each set is a number representing the number of commands your software has to run, followed by commands. Each command can be in one of the following two forms:
- – A portal joining and is added to the system. and are single words, no more than 255 characters each.
- – A query, asking if and are connected by any series of portals build so far. There will be at least one such query in each input set.
The output will contain 5 sets of outputs, answering each query command with
7 p Waterloo Toronto q Waterloo Toronto p Dubai Toronto p Montreal Vancouver q Montreal Waterloo p Dubai Vancouver q Montreal Waterloo 1 q Waterloo Waterloo
connected not connected connected connected