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 C2013 · MediumDFS & reachability

Emergency Phone 112

National Olympiad — Regional round

Submission name: no112C.cpp

Solve in Editor →

Problem summary

Only M undirected roads remain usable between N settlements. For each query X Y, determine whether travel between X and Y is possible using the usable roads.

Input

N M; M road pairs; Q; then Q query pairs.

Output

One string of Q bits: 1 for reachable and 0 for unreachable, in query order.

Constraints

2 ≤ N ≤ 1000; 1 ≤ M ≤ 2N; 1 ≤ Q ≤ 100,000.

Worked example

An independently prepared example for this explanation.

Input

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

Output

1011

Solution analysis

  1. Running a traversal for every call repeats work. Instead label all connected components once.
  2. Start an iterative DFS at each still-unlabeled vertex and give all reachable vertices the same component number.
  3. For a query, compare the two labels.
  4. Vertices in the same component can reach each other; different components cannot.

Why it works

The connected-component labels partition the undirected graph into its maximal reachable sets. Equality of labels is therefore equivalent to the existence of a path.

Complexity: O(N+M+Q) time, O(N+M) space.

Watch out. Output bits consecutively, not YES/NO or one answer per line. A settlement can always reach itself.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: The connected-component labels partition the undirected graph into its maximal reachable
// sets. Equality of labels is therefore equivalent to the existence of a path.
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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);
    }
    vector<int>component(n+1,-1);
    int count=0;
    for(int s=1;s<=n;++s){
        if(component[s]==-1){
            stack<int>st;
            st.push(s);
            component[s]=count;
            while(!st.empty()){
                int v=st.top();
                st.pop();
                for(int u:g[v]){
                    if(component[u]==-1){
                        component[u]=count;
                        st.push(u);
                    }
                }
            }
            ++count;
        }
    }
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        cout<<(component[a]==component[b]?'1':'0');
    }
    cout<<'\n';
}

Source: Arena Olimpiici ↗