cppAcademy
FROM LEARNING TO COMPETING

Expert.
Put your skills to the test.

Bulgarian Informatics Group A · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group A also includes challenging national-level problems. The 109 National-round tasks shared by Groups A and B retain their existing permanent URLs and explanations. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP A2009 · EasyComplement graphs

Roads

National Olympiad — Municipal round (2009 season)

Submission name: roads.cpp

Solve in Editor →

Problem summary

The existing undirected road network is connected. Replace it with all missing roads, and retain as few old roads as necessary to keep the resulting network connected.

Input

N M, followed by M old road endpoint pairs.

Output

The minimum number of old roads to retain.

Constraints

N ≤ 1000; M ≤ 500000; vertex numbers are 1 through N.

Worked example

Official statement example.

Input

4 4
1 2
2 3
3 4
4 1

Output

1

Solution analysis

  1. Store the old graph in an adjacency matrix. In the new graph, two distinct vertices are adjacent exactly when their matrix entry is absent.
  2. Find the number c of connected components in this complement graph by breadth-first search, testing all possible neighbors of each removed vertex. Then print c−1.
  3. The sample complement contains roads 1–3 and 2–4, giving two components. Keeping any one old road joining the two components makes the whole network connected.

Why it works

At least c−1 retained edges are needed to connect c components. Contract the complement components in the original connected graph. The contracted graph remains connected, and every edge between distinct components is an old road. A spanning tree supplies c−1 such roads, attaining the lower bound.

Complexity: O(N²+M) time and O(N²) space.

Watch out. Exclude a vertex from being its own complement neighbor.,Only the count of retained roads is requested.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: At least c−1 retained edges are needed to connect c components. Contract the complement
// components in the original connected graph.
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<unsigned char>>old(n,vector<unsigned char>(n,0));
    while(m--){
        int a,b;
        cin>>a>>b;
        old[a-1][b-1]=old[b-1][a-1]=1;
    }
    vector<bool>seen(n,false);
    int components=0;
    for(int start=0;start<n;++start){
        if(seen[start]){
            continue;
        }
        ++components;
        queue<int>q;
        q.push(start);
        seen[start]=true;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int v=0;v<n;++v){
                if(u!=v&&!old[u][v]&&!seen[v]){
                    seen[v]=true;
                    q.push(v);
                }
            }
        }
    }
    cout<<components-1<<'\n';
}

Source: Arena Olimpiici ↗