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 C2018 · EasyDFS & reachability

Quarantine

Sofia open - spring

Submission name: quarantine.cpp

Solve in Editor →

Problem summary

Contacts between people are listed in arbitrary chronological order. Starting from the named patient, count all other people who may be linked to the patient by a chain of contacts and should therefore also be quarantined.

Input

Zero or more lines of two names describing contacts. The final line has only the patient’s name. There is no initial count.

Output

The number of other people in the patient’s connected component.

Constraints

At most 10,000 people; names are single words shorter than 32 characters.

Worked example

An independently prepared example for this explanation.

Input

Ada Ben
Ben Cy
Dan Eve
Ada

Output

2

Solution analysis

  1. Assign an integer vertex ID to each name. Each contact becomes an undirected edge.
  2. The final one-name line identifies the starting vertex. Read lines, rather than assuming every record has two names.
  3. Run an iterative DFS from that vertex. Mark vertices when pushing them.
  4. Subtract one from the visited count because the patient is already in the clinic.

Why it works

Possible exposure passes along chains of contacts, exactly the vertices reachable in the undirected contact graph. DFS finds precisely that component.

Complexity: Expected O(V+E) time and O(V+E) space, including name lookup.

Watch out. The input has no N or M header. Duplicate contact records must not cause double-counting. An unconnected patient gives 0.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<sstream>
#include<string>
#include<unordered_map>
#include<vector>
#include<stack>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unordered_map<string,int>id;
    vector<vector<int>>g;
    auto getID=[&](const string&name){
        auto it=id.find(name);
        if(it!=id.end()){
            return it->second;
        }
        int v=(int)g.size();
        id[name]=v;
        g.push_back({});
        return v;
    };
    string line;
    int start=-1;
    while(getline(cin,line)){
        istringstream in(line);
        string a,b;
        if(!(in>>a)){
            continue;
        }
        int u=getID(a);
        if(in>>b){
            int v=getID(b);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        else{
            start=u;
            break;
        } // Final line: only the patient's name.
    }
    if(start==-1){
        return 0;
    }
    vector<bool>seen(g.size());
    stack<int>st;
    st.push(start);
    seen[start]=true;
    int count=0;
    while(!st.empty()){
        int v=st.top();
        st.pop();
        ++count;
        for(int u:g[v]){
            if(!seen[u]){
                seen[u]=true;
                st.push(u);
            }
        }
    }
    cout<<count-1<<'\n';
}

Source: Arena Olimpiici ↗