UVa 10158

From Algorithmist
Jump to navigation Jump to search

10158 - War[edit]

Summary[edit]

We have to manage the diplomatic relations between countries at a time of war. The relations between countries follow logical rules such as "If x is an enemy of y and y is an enemy of z, then x is a friend of z." We must keep a data structure that allows the countries to form alliances and enemies.

Explanation[edit]

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

Use the normal Union Find to keep the friend groups, then keep a pointer to the enemy.

Gotcha's[edit]

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.

Solutions[edit]

Input[edit]

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
0 0 0

Output[edit]

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