cppAcademy
FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 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 B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP B2013 · MediumDisjoint sets

Emergency Road Queries

National Olympiad — Regional round (2013 season)

Submission name: no112B.cpp

Solve in Editor →

Problem summary

Maintain connectivity of towns as initially snow-covered roads are reopened. Type 1 asks whether two towns are connected; type 2 adds a usable undirected road.

Input

N M, M usable roads, Q, then Q triples type X Y.

Output

One bit string in query order: 1 for connected, 0 otherwise.

Constraints

N≤1000; M≤2N; Q≤1000000. Between 30% and 35% of calls have type 2.

Worked example

An independently prepared example for this explanation.

Input

9 8
1 2
3 4
5 6
7 8
9 5
7 2
8 2
6 9
6
1 1 8
1 6 2
2 7 1
1 4 7
2 2 3
1 4 7

Output

1001

Solution analysis

  1. Connectivity components only merge because no road closes again. A disjoint-set union structure maintains a representative for each component.
  2. Initialize singleton sets and unite every initial road. For a reopening, unite its endpoints; for a query, compare their representatives. Union by size and path compression keep these operations nearly constant in amortized time.
  3. In the sample, 1 and 8 are initially connected, but 6 and 2 are not. Reopening 7–1 changes nothing. Towns 4 and 7 become connected only after reopening 2–3, giving the bit string 1001.

Why it works

Initially the sets are exactly the connected components after processing all initial edges. An added road merges precisely its endpoint components, preserving that invariant. Therefore equal representatives are equivalent to reachability at each query time.

Complexity: O((N+M+Q)α(N)) time, where α is the inverse Ackermann function; O(N) extra space while answers are streamed.

Watch out. Do not answer only direct adjacency. Duplicate roads are harmless, and a town is connected to itself.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
// Algorithm: Connectivity components only merge because no road closes again.
using namespace std;
struct DisjointSet{
    vector<int>parent;
    vector<int>size;
    explicit DisjointSet(int n):parent(n+1),size(n+1,1){
        iota(parent.begin(),parent.end(),0);
    }
    int find(int vertex){
        while(vertex!=parent[vertex]){
            parent[vertex]=parent[parent[vertex]];
            vertex=parent[vertex];
        }
        return vertex;
    }
    void unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return;
        }
        if(size[a]<size[b]){
            swap(a,b);
        }
        parent[b]=a;
        size[a]+=size[b];
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int towns,roads;
    cin>>towns>>roads;
    DisjointSet components(towns);
    for(int i=0;i<roads;i++){
        int a,b;
        cin>>a>>b;
        components.unite(a,b);
    }
    int calls;
    cin>>calls;
    while(calls--){
        int type,a,b;
        cin>>type>>a>>b;
        if(type==2){
            components.unite(a,b);
        }
        else{
            cout<<(components.find(a)==components.find(b)?'1':'0');
        }
    }
    cout<<'\n';
}

Source: Arena Olimpiici ↗