Internet Problem Solving Contest

IPSC 2004

Solution to Problem E – Electrical Circuits

Let us represent the unconnected contacts as nodes of a graph and pairs of compatible contacts will be edges. Now, the problem is to count the number of perfect matchings. In general this problem is very hard. To solve it, we must exploit special properties of graphs given in the inputs.

Otherwise absolutely useless coordinates in the input file were useful for drawing the graphs so that it is easy to see their special properties. See the drawings: easy.ps and hard.ps or hard.png. The drawings were created by this short utility.

We can see that all graphs in the easy input file are composed of rather small connected components. In each component, the number of perfect matchings may be determined by exhaustive search that tries all possible matchings. The number of perfect matchings of a graph is the product of numbers of perfect matchings of all its connected components.

In the hard input, there is a graph with four different kinds of connected components:

The total number of perfect matchings of the graph is again the product of numbers of perfect matchings of all connected components.