UVa 793

From Algorithmist
Jump to navigation Jump to search

793 - Network Connections[edit]

Summary[edit]

We must help a network administrator determine which computers are connected to each other. We must handle two kinds of requests. There is a connection request, which puts a direct link between two machines, and a query request in which we must determine if two machines are able to communicate with one another through one or more hops.

Explanation[edit]

This is a pretty straight forward Union Find problem, with no real frills or interesting twists.

Gotcha's[edit]

This is a Multiple Input problem, even though not shown in the sample input given on the UVa site. Make sure you pass the input listed here.

Input[edit]

2

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5

Output[edit]

1,2

1,2

Solutions[edit]

References[edit]

Multiple Input Problems