Adding Edges
Time limit2sMemory limit128 MB
Find the minimum number of edges to add to a graph so it becomes connected and admits an Euler trail.
- Level
Medium7 of 10
- Topics
- Union-find, Graph, Greedy, Math
- Solved
- No attempts yet
Problem
Given an undirected graph, add as few edges as possible so that the resulting graph is connected and has an Euler trail.
An Euler trail is a path that uses every edge exactly once. The starting vertex and ending vertex may be the same or different.
Input
The first line contains the number of vertices V and the number of edges E.
2 <= V <= 1,000
1 <= E <= V * (V - 1) / 2
The vertices are numbered from 1 to V. Each of the next E lines contains two distinct vertices a and b that form an edge. All edges in the input are distinct.
Output
Print the minimum number of edges that must be added.