Add the Fewest Bridges for an Euler Tour
Autumn Tournament (2017)
Submission name: bridges.cpp
Problem summary
Add the fewest undirected bridges so the whole island region forms a connected graph admitting a closed walk using every bridge exactly once. Parallel bridges are allowed. Output a minimum set of new bridges.
Source clarification. The official editorial connects every connected component of the island graph. This follows that intended connected-region interpretation, including isolated islands: https://infos.infosbg.com/files/Contests/ETI/2017/B/analyses/B2_bridges_analysis.docx
Input
N M, followed by M endpoint pairs; islands are numbered1…N.
Output
K, then K new bridge endpoint pairs. If nothing is needed, print only0.
Constraints
N ≤1000; M ≤10000.
Worked example
Original statement sample input; one valid output from the implementation below.
Input
4 7 1 2 2 3 3 2 2 1 1 4 2 4 3 4
Output
2 1 4 3 2
Solution analysis
- A connected undirected multigraph has an Euler circuit exactly when all degrees are even. First find connected components and list each component’s odd-degree vertices; their count is always even. With one component, pair these odd vertices and add one bridge per pair.
- With several components, reserve two connection ports per component. If it has odd vertices, reserve its first two and pair the remaining odds internally. If it has no odd vertices, use the same representative island as both ports. Connect the components in a cycle, using each component’s outgoing port and the next component’s incoming port.
- This cycle makes the graph connected. Each reserved odd vertex gets one new incident edge; a repeated even representative gets two. Internal pairings also flip exactly the intended odd degrees. In the sample all four vertices are odd, and adding1–2 and3–4 makes every degree even.
Why it works
For multiple components, a component with o odd vertices needs at least max(2,o) new incident edge ends: o are required to repair odd parities, while an all-even component needs a positive even number of cross-component ends to join an Eulerian graph. Every added edge contributes two ends, giving the lower bound Σmax(2,o)/2. The cycle-plus-pairing construction attains this bound and satisfies connectivity and all parities. The one-component case needs exactly o/2 edges.
Watch out. Count parallel edges separately. Do not connect components with only a spanning tree: its endpoints may have odd degree. One already connected even-degree component needs0 bridges, not a one-component cycle.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>>graph(n+1);
vector<int>degree(n+1),seen(n+1);
for(int i=0;i<m;++i){
int u,v;
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
++degree[u];
++degree[v];
}
vector<vector<int>>odds;
vector<int>representatives;
for(int start=1;start<=n;++start){
if(seen[start]){
continue;
}
representatives.push_back(start);
odds.push_back({});
vector<int>pending{start};
seen[start]=1;
while(!pending.empty()){
int u=pending.back();
pending.pop_back();
if(degree[u]%2==1){
odds.back().push_back(u);
}
for(int v:graph[u]){
if(!seen[v]){
seen[v]=1;
pending.push_back(v);
}
}
}
}
vector<pair<int,int>>added;
int components=static_cast<int>(odds.size());
if(components==1){
for(int i=0;i<static_cast<int>(odds[0].size());i+=2){
added.push_back({odds[0][i],odds[0][i+1]});
}
}
else{
vector<array<int,2>>ports(components);
for(int c=0;c<components;++c){
if(odds[c].empty()){
ports[c]={representatives[c],representatives[c]};
}
else{
ports[c]={odds[c][0],odds[c][1]};
for(int i=2;i<static_cast<int>(odds[c].size());i+=2){
added.push_back({odds[c][i],odds[c][i+1]});
}
}
}
// Two reserved ends per component form a connecting cycle.
for(int c=0;c<components;++c){
added.push_back({ports[c][1],ports[(c+1)%components][0]});
}
}
cout<<added.size()<<'\n';
for(auto[u,v]:added){
cout<<u<<' '<<v<<'\n';
}
}