Maximum Ball Colors
National Olympiad — Regional round (2015 season)
Submission name: balls.cpp
Problem summary
N balls may use different colors, but every specified pair must share a color. Find the maximum possible number of colors.
Input
N M and M ball pairs.
Output
The maximum number of colors.
Constraints
N < 10^9; M < 100000; repeated pairs allowed.
Worked example
An independently prepared example for this explanation.
Input
10 5 1 2 1 3 2 3 1 4 2 1
Output
7
Solution analysis
- The equality constraints are transitive: all balls in one connected component must have the same color, while different components may choose distinct colors.
- Begin with N components. Compress only labels that appear in the M pairs, then process pairs with a disjoint set structure. Every successful union reduces the component count by one. Unmentioned balls remain separate without being stored.
- In the example, labels 1,2,3,4 become one component through three successful unions. The repeated and redundant constraints cause no change. Hence 10−3=7 colors are possible.
Why it works
The connected components are exactly the equivalence classes forced equal by all constraints. Union operations maintain those classes, reducing their count exactly when two previously separate classes merge. One unique color per final class satisfies every constraint and attains the count.
Watch out. N may be a billion. Do not decrement for redundant or repeated constraints.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
// Algorithm: The equality constraints are transitive: all balls in one connected component must
// have the same color, while different components may choose distinct colors.
using namespace std;
struct DisjointSet{
vector<int>parent,size;
explicit DisjointSet(int n):parent(n),size(n,1){
iota(parent.begin(),parent.end(),0);
}
int find(int v){
if(parent[v]!=v){
parent[v]=find(parent[v]);
}
return parent[v];
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b){
return false;
}
if(size[a]<size[b]){
swap(a,b);
}
parent[b]=a;
size[a]+=size[b];
return true;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<pair<int,int>>edges(m);
vector<int>labels;
for(auto&edge:edges){
cin>>edge.first>>edge.second;
labels.push_back(edge.first);
labels.push_back(edge.second);
}
sort(labels.begin(),labels.end());
labels.erase(unique(labels.begin(),labels.end()),labels.end());
DisjointSet dsu(static_cast<int>(labels.size()));
int components=n;
for(auto edge:edges){
int a=static_cast<int>(lower_bound(labels.begin(),labels.end(),edge.first)-labels.begin());
int b=static_cast<int>(lower_bound(labels.begin(),labels.end(),edge.second)-labels.begin());
if(dsu.unite(a,b)){
--components;
}
}
cout<<components<<'\n';
}