PROBLEM LINK:
Author: Hussain Kara Fallah
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal
AUTHOR’S AND TESTER’S SOLUTIONS:
AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555
DIFFICULTY -
Medium
PREREQUISITES -
DSU (Disjoint Set Union)
PROBLEM -
Given a graph of N nodes and M edges. For all d from 0 to N - 1 calculate the minimum no. of edges that need to be added to make the graph connected, when all the edges whose at least one end point has degree less than or equal to d is deleted.
QUICK EXPLANATION -
This question requires DSU and basic graph theory. We can simulate the process in reverse order, that is from d = N - 1 to d = 0, doing DSU of components and the answer for every d is the no. of components - 1.
EXPLANATION -
Firstly we would make an array of vectors, where in the x_{th} vector we store all the nodes whose degree is x.
Observation 1 - For any disconnected graph we can easily prove that the minimum no. of edges needed to be added to make the graph connected is equal to the no. of components - 1. Suppose we have arranged the components in line from left to right. Now you can merge any two adjacent components by adding an edge. So, you will require no. of components - 1 edges to be added.
The naive approach for this question would be to loop for d from 0 to N - 1, and for each d make the new graph with the deleted edges and do multiple DFS on this new graph to count the total no. of components and then print the answer as no. of components - 1.
But this can be optimised using the second critical observation which is -
Observation 2 - If we process d in reverse order, i.e from N - 1 to 0 then it is more efficient because the edges would only be added and not destroyed, which is a feature that DSU can support. The intuition behind this method is that for each d all the edges to be deleted are a union of those that need to be deleted for d - 1 along with some other edges specific to this d. This shows us that it is actually a completely disconnected graph, i.e all the nodes have degree = 0, when d = N - 1. And as the d is decreased, more and more edges are added. Now when d moves from d = x to d = x - 1, then all the nodes having degree = x are activated and processed (in simple term the edges which have one end point as these nodes are undeleted), which can be supported by the DSU.
So for the expected solution we actually process d from N - 1 to 0 and for each d we first store the current no. of components - 1 as the answer for this d and then activate all the nodes that are in the d_{th} vector, i.e all the nodes that have degree exactly equal to d. Now we process these activated nodes, here processing a node means to join that node to all its immediate neighbours which are active using DSU and we need to constantly maintain the count of the total no. of components while performing DSU.
Refer to the given below C++ implementation for more details -
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
vector<int> adj[N], V[N];
int deg[N], p[N], sz[N], ans[N];
bool active[N];
int components;
int par(int x){
if(p[x] != x) p[x] = par(p[x]);
return p[x];
}
void dsu(int a, int b){
int p1 = par(a), p2 = par(b);
if(p1 == p2) return ;
if(sz[p1] < sz[p2]) swap(p1, p2);
sz[p1] += sz[p2];
p[p2] = p1;
components--;
}
void solve(){
for(int i = 0; i < N; i++){
adj[i].clear();
V[i].clear();
deg[i] = 0;
active[i] = 0;
}
int n, m, u, v;
cin>>n>>m;
while(m--){
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++, deg[v]++;
}
components = n;
for(int i = 1; i <= n; i++){
p[i] = i, sz[i] = 1;
V[deg[i]].push_back(i);
}
for(int i = n - 1; i >= 0; i--){
ans[i] = components - 1;
for(auto u : V[i]) active[u] = 1;
for(auto u : V[i]){
for(auto v : adj[u]){
if(active[v] == 0) continue;
dsu(u, v);
}
}
}
for(int i = 0; i < n; i++) cout<<ans[i]<<" ";
cout<<endl;
}
int main(){
int t;
cin>>t;
while(t--) solve();
}
Time Complexity -
The time complexity of an operation in DSU with path compression is \alpha(n) and the no. of times it is done is equal to the number of edges in the graph. Therefore the complexity of the solution is O((N + M) * \alpha(N)). Since the \alpha(n) is a small constant (around 4) for all practical values of N therefore it can be ignored as a constant factor also in the complexity analysis.
