DWITE Online Computer Programming Contest

Portals Check

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 file DATA5.txt will contain 5 test sets. The first line of each set is a number 1 ≤ N ≤ 100,000 representing the number of commands your software has to run, followed by N commands. Each command can be in one of the following two forms:

The output file OUT5.txt will contain 5 sets of outputs, answering each query command with connected or not connected.

Note: In the second test case, Waterloo is not connected to itself, as no portals have been built.

Sample Input (first 2 shown):
p Waterloo Toronto
q Waterloo Toronto
p Dubai Toronto
p Montreal Vancouver
q Montreal Waterloo
p Dubai Vancouver
q Montreal Waterloo
q Waterloo Waterloo
Sample Output (first 2 shown):
not connected
not connected