cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP B2008 · MediumBFS & shortest paths

Net of Ropes

Autumn tournament

Submission name: rings.cpp

Solve in Editor →

Problem summary

A connected net consists of rings joined by equal-length ropes. Pull two rings A and B apart until the net is taut. Rings on at least one shortest A–B route become aligned; the others hang. Count hanging rings for each of two supplied pairs.

Input

N M; M undirected ring pairs; then exactly two pairs A B.

Output

Two hanging-ring counts on one line, in query order.

Constraints

6 ≤ N ≤ 999; vertices are 1…N; A≠B; the network is connected.

Worked example

An independently prepared example for this explanation.

Input

6 5
1 2
2 3
3 4
4 5
3 6
1 5
1 6

Output

1 2

Solution analysis

  1. Run BFS from A to obtain dA and from B to obtain dB.
  2. The taut endpoint separation is the length D=dA[B] of a shortest route.
  3. A vertex v belongs to a shortest route exactly when dA[v]+dB[v]=D.
  4. Count vertices failing that equality. Repeat for the second endpoint pair.

Why it works

A shortest route through v has prefix and suffix lengths summing to D. Conversely, equality concatenates shortest endpoint paths into a shortest A–B walk; a shortest walk cannot contain a cycle, so v lies on a shortest path.

Complexity: O(N+M) time per endpoint pair, O(N+M) space.

Watch out. Count the union of all shortest routes. Reconstructing only one shortest path misses rings on alternative routes.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: A shortest route through v has prefix and suffix lengths summing to D. Conversely,
// equality concatenates shortest endpoint paths into a shortest A–B walk; a shortest walk cannot
// contain a cycle, so v lies on a shortest path.
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int>bfs(const vector<vector<int>>&g,int s){
    vector<int>d(g.size(),-1);
    queue<int>q;
    d[s]=0;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int u:g[v]){
            if(d[u]==-1){
                d[u]=d[v]+1;
                q.push(u);
            }
        }
    }
    return d;
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>g(n+1);
    for(int i=0;i<m;++i){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int query=0;query<2;++query){
        int a,b;
        cin>>a>>b;
        auto da=bfs(g,a),db=bfs(g,b);
        int hanging=0;
        for(int v=1;v<=n;++v){
            if(da[v]+db[v]!=da[b]){
                ++hanging;
            }
        }
        if(query){
            cout<<' ';
        }
        cout<<hanging;
    }
    cout<<'\n';
}

Source: Arena Olimpiici ↗