Pairs
Sofia open - autumn
Submission name: pairs.cpp
Problem summary
For each given pair of people, it is known that they belong to the same city. People from different cities cannot meet. Find the maximum number of unordered pairs that could be prevented from meeting, consistently with the given information.
Input
N M; then M pairs of person IDs, numbered 0…N−1.
Output
The maximum number of pairs from different possible cities.
Constraints
1 ≤ N,M ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
5 2 0 1 2 3
Output
8
Solution analysis
- Every same-city relationship merges two DSU sets. Transitivity forces a whole component to be in one city.
- To maximize separated pairs, assign different components to different cities.
- Start with all N(N−1)/2 pairs. A merge of sets of sizes a and b makes a·b previously separate pairs necessarily same-city.
- Subtract a·b only when the two representatives differ. Repeated relationships make no further change.
Why it works
Components are the smallest city groups forced by the information. Keeping them separate maximizes cross-city pairs. Merging two groups converts exactly the pairs with one endpoint in each group into same-city pairs.
Watch out. The answer can approach 5×10¹¹. Use long long for pair counts and the product of component sizes. IDs are zero-based in the original problem.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Components are the smallest city groups forced by the information. Keeping them separate
// maximizes cross-city pairs.
#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
struct DSU{
vector<int>p,sz;
DSU(int n):p(n),sz(n,1){
iota(p.begin(),p.end(),0);
}
int find(int v){
return p[v]==v?v:p[v]=find(p[v]);
}
long long merge(int a,int b){
a=find(a);
b=find(b);
if(a==b){
return 0;
}
if(sz[a]<sz[b]){
swap(a,b);
}
long long newlySame=1LL*sz[a]*sz[b];
p[b]=a;
sz[a]+=sz[b];
return newlySame;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
DSU ds(n);
long long answer=1LL*n*(n-1)/2;
while(m--){
int a,b;
cin>>a>>b;
answer-=ds.merge(a,b);
}
cout<<answer<<'\n';
}