The problem can be restated as requiring that one adds the minimum number of edges to make the graph biconnected. The first step is to identify the existing biconnected components; refer to your favourite algorithms textbook to see what a biconnected component is and how to identify one; be aware though that there are two variants of bi-connectivity, depending on whether separate routes must be vertex-disjoint or edge-disjoint; in this case they must be edge-disjoint, so biconnected components are separated by articulation edges (vertex-disjoint biconnectivity is more common and probably what your favourite textbook will discuss, but the algorithms involved are very similar).
We will never need to add edges within a biconnected component, so for the purposes of the problem we can collapse each biconnected component to a single vertex. This will leave the graph as a tree. Each leaf will need a new edge added (since there is currently only one road to its parent), so at least ceil(leaves / 2) edges must be added. It is also possible to show that this number is sufficient (hint: joining the left-most and right-most leaf and re-collapsing the newly created biconnected component will almost always reduce the number of leaves by 2). So it is sufficient to count the leaves; you don't actually need to work out which new paths to add.
The solution below was written for a different formulation of the problem and includes some coaching-file output. Ignore that :) .
#include <iostream> #include <fstream> #include <algorithm> #include <climits> #include <cassert> #include <vector> #include <cstddef> #include <stack> using namespace std; #define MAXC 5000 #define MAXR 10000 struct road { int target; int dual; road() {} road(int _target, int _dual) : target(_target), dual(_dual) {} }; struct castle { int id; int top; int parent; int bcc; vector<road> roads; castle() : id(-1), top(-1), parent(-1), bcc(-1), roads() {} }; static int C; static castle castles[MAXC]; #ifndef NDEBUG static bool connected() { stack<int> todo; vector<bool> seen(C, false); int remain = C; todo.push(0); seen[0] = true; while (!todo.empty()) { int cur = todo.top(); todo.pop(); remain--; seen[cur] = true; for (size_t i = 0; i < castles[cur].roads.size(); i++) { int nxt = castles[cur].roads[i].target; if (!seen[nxt]) { todo.push(nxt); seen[nxt] = true; } } } return remain == 0; } #endif static void readin() { int R, x, y; ifstream in("rpaths.in"); in.exceptions(ios::failbit); in >> C >> R; assert(3 <= C && C <= MAXC); assert(C - 1 <= R && R <= MAXR); for (int i = 0; i < R; i++) { in >> x >> y; assert(x != y); assert(1 <= x && x <= C); assert(1 <= y && y <= C); x--; y--; castles[x].roads.push_back(road(y, castles[y].roads.size())); castles[y].roads.push_back(road(x, castles[x].roads.size() - 1)); } assert(connected()); } static int recurse(int cur, int up_edge) { static int id_pool = 0; static stack<int> bcc; int leaves = 0; castles[cur].id = id_pool++; castles[cur].top = cur; bcc.push(cur); for (size_t i = 0; i < castles[cur].roads.size(); i++) { int nxt = castles[cur].roads[i].target; if ((int) i == up_edge) continue; if (castles[nxt].id == -1) { castles[nxt].parent = cur; leaves += recurse(nxt, castles[cur].roads[i].dual); } if (castles[castles[nxt].top].id < castles[castles[cur].top].id) castles[cur].top = castles[nxt].top; } if (castles[cur].top == cur) { while (bcc.top() != cur) { castles[bcc.top()].bcc = cur; bcc.pop(); } castles[cur].bcc = cur; bcc.pop(); if (leaves == 0) leaves = 1; } return leaves; } static bool bridge(int c, int edge) { return castles[c].top == c && castles[c].roads[edge].target == castles[c].parent; } static int solve() { int leaves = recurse(0, -1); int root_children = 0; for (int i = 1; i < C; i++) { int p = castles[i].parent; if (castles[i].top == i && castles[p].bcc == 0) root_children++; } ofstream dot("roads.dot"); dot << "graph G {\n" << " node [shape=circle,fontsize=10,width=0.2,label=\"\"]\n"; for (int i = 0; i < C; i++) for (size_t j = 0; j < castles[i].roads.size(); j++) { int trg = castles[i].roads[j].target; if (trg < i) continue; dot << " " << i + 1 << " -- " << trg + 1; if (bridge(i, j) || bridge(trg, castles[i].roads[j].dual)) dot << " [style=bold]"; else dot << " [len=0.3]"; dot << "\n"; } dot << "}\n"; if (root_children == 0) return 0; else if (root_children == 1) leaves++; return (leaves + 1) / 2; } int main() { readin(); ofstream out("rpaths.out"); out << solve() << "\n"; return 0; }