SPOJ PRIMIT

From Algorithmist
Jump to navigation Jump to search

211 (PRIMIT) Primitivus Recurencis[edit]

Summary[edit]

This problem asks for you to calculate the minimum number of edges to be added to make a given directed graph Eulerian.

Explanation[edit]

Notice that no additional cycles should be added to the graph. This implies that all the weakly connected components(let their number be C) should be made Eulerian first and additionally C-1 edges should be added. To make a (weakly)connected directed graph eulerian, either all the vertices have equal in-degree and out-degree or all except exactly 2 have equal incoming and outcoming edges. One of those two vertices should have one outgoing edge more than its incoming edges and the other should have one outgoing edge less than its incoming edges.

            Clearly, a linear implementation is possible.

Input[edit]

1
2
1 2
2 1

Output[edit]

3