This is a problem from an algorithmic competition from a few years back. It has a very simple description, but I don't see any algorithm to solve it efficiently. I am not looking for an implementation, but a general idea how to solve this problem.
Description: We would like to build a domino chain from all tiles we are given (as in domino two tiles can be joined iff the same number appears on its adjacent sides). This isn't always possible. Therefore we should output the minimum number of tiles it is necessary to add to build the chain.
Input: n pairs of integers in the range [0, 10000] n <= 1000000 (so the algorithm can be O(nlogn) at worst)
Output: How many tiles (at least) should be added.
2 1 2 3 4 5
Explanation: (1 2) (2 3) ! (4 5) It's impossible to build the chain without adding any tiles. Adding one tile ((3 4)) where "!" stands creates a correct chain containing all tiles, therefore the answer is 1.