UVa 10158

From Algorithmist

Contents 1 10158 - War 2 Summary 3 Explanation 4 Gotcha's 5 Input 6 Output

[edit] 10158 - War

• http://acm.uva.es/p/v101/10158.html

[edit] Summary

We have to manage the diplomatic relations between countries at a time of war. The countries follow logical and interesting rules such as "the enemy of my enemy is my friend." We must keep a data structure that allows the countries to form alliances and enemies.

[edit] Explanation

This is a Union Find problem with a nice twist. Instead of just maintaining inclusion within a set, we also have to maintain a corresponding "enemy" set.

[edit] Gotcha's

There are quite a few cases to handle. The sample input listed with the problem statement is woefully inadequate at covering all the cases. There are really four cases (three after symettry) to handle when performing both a setFriends and a setEnemies operation. The number of groups of enemies between the two countries becoming friends or foes can be either 0, 1, or 2.

[edit] Input

10
4 4 1
1 6 5
4 2 3
3 1 0
2 5 3
1 2 5
2 9 8
1 8 0
4 9 3
2 3 0
4 7 3
2 4 9
1 4 2
2 6 3
1 6 9
1 2 1
1 7 5
2 1 8
1 3 0
1 7 0
1 2 8
3 5 6
4 2 7
2 0 3
1 6 7
2 4 8
4 4 6
1 9 4
4 2 1
4 3 0

[edit] Output

0
0
0
0
0
-1
-1
-1
1
0
-1
0
-1
0
1