UVa 793

From Algorithmist

Contents 1 793 - Network Connections 2 Summary 3 Explanation 4 Gotcha's 5 Input 6 Output 7 References

[edit] 793 - Network Connections

• http://acm.uva.es/p/v7/793.html

[edit] Summary

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.

[edit] Explanation

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

[edit] Gotcha's

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.

[edit] Input

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

[edit] Output

1,2

1,2

[edit] References

Multiple Input Problems