# PROBLEM LINK:

Author: Arthur Nascimento

Tester: Felipe Mota

Editorialist: Rajarshi Basu

# DIFFICULTY:

Medium

# PREREQUISITES:

Implementation, Logic, DSU, Small To Large

# PROBLEM:

We are given a graph with N \leq 10^5 nodes and M \leq 2*10^5 edges. The graph may have multiple edges between two cities, no self-loops, and might not be connected. We should make a new graph, such that it is connected. Let the degree of each node i before be degPrev_i and the degrees of each node i in the new graph be degNow_i. We have to minimise the value of \sum_{i=1}^{n} |degNow_i - degPrev_i|, which is denoted as the *inconvenience*.

# QUICK EXPLANATION:

## How fast can you read this?

- We will have several connected components, some of which are trees, and some which are not trees. First, all the non-tree components can be connected without changing the degree of each node. Just connect one of their non-spanning-tree-edges in cyclic order
- We can use a non-spanning-tree-edge of a non-tree component, and connect a tree component with it without increasing the
inconvenience. (Think how)- We can use a non-spanning-tree-edge of a non-tree component to connect two tree components to it, by adding 2 to the
inconvenience.- If all non-spanning-tree-edges are used up, just add extra edges till everything is connected. Extra edges combine two components at the cost of 2 to the overall
inconvenience.- Maintain the non-spanning-tree-edge information using DSU with Small to Large Merging.

# EXPLANATION:

## Observation 1

The problem wants us to keep the degrees as similar to the original graph as possible. Thus, it seems that the best thing for us to do is try to keep as many edges of the original graph and make everything connected using as few additional edges/ edge changes possible.

## Observation 2

For each of the connected component, it can be of two types. Let us assume that there are C nodes in the component. Then:

- If there are exactly C-1 edges, we call it a tree-component, since itâ€™s in the form of a tree. If we remove any edges, then it no longer remains connected.
- If there are K edges, where K > C-1, then we call it a non-tree component. In particular, there will be K - (C-1)
that, even if removed, will not disconnect the component. We will call all such edge anextra edgesExtraEdge.

## Observation 3 - Handling Some Simplifications

Itâ€™s often a good idea to simplify our problem into smaller and easier parts. For example, here, letâ€™s just assume all our components were either tree components or non-tree components.

- If all were Tree components, and there were x of them, the best-case scenario is adding x-1 new edges to make everything connected, thereby adding a total of 2*(x-1) to the total inconvenience.
- What if all the componentâ€™s are non-Tree components? Well, just take one
ExtraEdgefrom each component, and use them to connect the components in a cycle order.

## Confused with connecting the Non-Tree Components?

Here, see this diagram. Hopefully, it will clear things up. The left side has 4 non-tree component, while the right side shows how they can be

cyclicallyconnected. (If it reminds you of the Transition State of Wittig Reaction, I am sorry for the PTSD).

## Observation 4

Letâ€™s get back to the original problem.

After connecting all the Non-Tree Components into a single (super) Non-Tree component (exercise: figure out why they will still be non-tree, hint: see diagram in

Observation 3), weâ€™ll still have some Tree Components left.

Now, we can connect a Tree Component with the (super) Non-Tree Component, by using anExtraEdge, without adding anyinconvenience.

We will call this

Operation 1

## We love diagrams so here is another

## EdgeCase?

To do this operation, we need atleast 2 nodes in the component.

## Observation 5

In

Operation 1, we connected a single Tree Component to the super NonTree component by using 1ExtraEdge. However, can we add two Tree components by using 1ExtraEdge?

We will call this

Operation 2

## EdgeCase

There arenâ€™t any. Even if there is exactly 1 node in the component, this operation is possible.

## Observation 6

What if we exhaust all

ExtraEdges? Well, we can just add new edges to connect each Tree Component to the super- NonTree Component. Each of these adds 2 to the totalinconvenience.

We will call these

Operation 3

## Putting Everything together

So here is what we will do:

- First, we form the super-Non-Tree component.
- Next, we do
Operation 1as long as possible. Thus, we either run out of Tree components, in which case we are done, or we run out ofExtraEdges.- In case we run out of
ExtraEdges, keep doingOperation 3till everything becomes connected.

## Wait, we never use Operation 2?

TL;DR: No.

## Here's why

Letâ€™s say we have x

ExtraEdgesand y Tree Components. Now, let us assume y>x since that is the only interesting case. The only difference betweenOperation 1andOperation 2is that,Operation 1connects 1 Tree component with 0inconveniencewhileOperation 2connects 2 Tree components to the super Non Tree Component with total cost of 2. Each of them use up 1ExtraEdge. Further, in both cases, we need to useOperation 3to connect the remaining stuff.

- Now, if we used
Operation 1x times, our total inconvenience = x*0 + (y-x)*2

\implies inconvenience = 2*y - 2*x.- If we used
Operation 2z times, andOperation 1(x-z) times, then

inconvenience = (x-z)*0 + z*2 + (y - 2*z - (x-z))*2

\implies inconvenience= 2*z + 2*(y-2*z - x + z)

\implies inconvenience= 2*z + 2*(y-z-x)

\implies inconvenience= 2*z + 2*y - 2*z - 2*x

\implies inconvenience= 2*y - 2*x.- Hence we see that we obtain the same
inconveniencewhether or not we use anyOperation 2.

## Implementation

First, maintain all the

ExtraEdgesfor the components in the graph using DSU and small-to-large merging inside the DSU (see Editorialist code for details).

Also maintain the adjacency lists of all the nodes as multisets.

Lastly, do all the operations by just iterating over the list ofExtraEdgesand Tree components. Again, see Editorialist code for more details.

## Time Complexity

Since we are using multiple operations using

sets, and small-to-large inside the DSU, our overall complexity is O(nlogn).

# QUICK REMINDERS:

There can be multi-edges remember? Donâ€™t forget to use **multiset** instead of *set* to represent the adjacency lists.

**C++ NOTE:** While erasing in a multiset, we have to pass in an iterator to delete one occurrence. If we just pass a value, the multiset erases all the occurrences of the value.

# SOLUTIONS:

## Setter's Code

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector<int> uf(n);
iota(uf.begin(), uf.end(), 0);
vector<vector<pair<int,int>>> indep(n), spanning(n);
function<int(int)> find = [&](int x){
return x == uf[x] ? x : uf[x] = find(uf[x]);
};
auto merge = [&](vector<pair<int,int>> &a, vector<pair<int,int>> &b){
if(a.size() < b.size()){
for(auto & e : a) b.push_back(e);
swap(a, b);
} else {
for(auto & e : b) a.push_back(e);
}
b.clear();
};
auto join = [&](int u, int v){
int fu = find(u);
int fv = find(v);
if(fu == fv){
indep[fu].push_back({u, v});
} else {
spanning[fu].push_back({u, v});
merge(indep[fu], indep[fv]);
merge(spanning[fu], spanning[fv]);
uf[fv] = fu;
}
};
int incovenience = 0;
auto incov_join = [&](int u, int v){
u = find(u);
v = find(v);
if(indep[u].size() < indep[v].size()) swap(u, v);
if(indep[u].size() + indep[v].size() == 0){
incovenience += 2;
spanning[u].push_back({u, v});
merge(spanning[u], spanning[v]);
} else {
auto edge_u = indep[u].back(); indep[u].pop_back();
if (indep[v].empty()) {
auto edge_v = spanning[v].back(); spanning[v].pop_back();
spanning[u].push_back({edge_u.first, edge_v.first});
spanning[u].push_back({edge_u.second, edge_v.second});
} else {
auto edge_v = indep[v].back(); indep[v].pop_back();
spanning[u].push_back({edge_u.first, edge_v.first});
indep[u].push_back({edge_u.second, edge_v.second});
}
merge(spanning[u], spanning[v]);
merge(indep[u], indep[v]);
}
uf[v] = u;
};
vector<int> deg(n);
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
u--; v--;
join(u, v);
deg[u]++;
deg[v]++;
}
vector<pair<int,int>> comp;
vector<int> nodes;
for(int i = 0; i < n; i++) if(i == uf[i] && spanning[i].empty()) {
nodes.push_back(i);
}
for(int i = 0; i < n; i++) if(i == uf[i] && !spanning[i].empty()) {
comp.push_back({indep[i].size(), i});
}
if (comp.empty()) {
cout << (n - 1) * 2 << ' ' << n - 1 << '\n';
for(int i = 1; i < n; i++){
cout << nodes[0] + 1 << ' ' << nodes[i] + 1 << '\n';
}
continue;
}
sort(comp.rbegin(), comp.rend());
for(int i = 1; i < comp.size(); i++){
incov_join(comp[0].second, comp[i].second);
}
int root = find(comp[0].second);
while(indep[root].size() > 0 && nodes.size() >= 2){
auto edge_i = indep[root].back(); indep[root].pop_back();
int u = nodes.back(); nodes.pop_back();
int v = nodes.back(); nodes.pop_back();
spanning[root].push_back({u, edge_i.first});
spanning[root].push_back({v, edge_i.second});
incovenience += 2;
}
if(nodes.size()){
spanning[root].push_back({root, nodes.back()});
incovenience += 2;
}
merge(spanning[root], indep[root]);
cout << incovenience << ' ' << spanning[root].size() << '\n';
for(auto e : spanning[root]){
deg[e.first]--;
deg[e.second]--;
assert(e.first != e.second);
cout << e.first + 1 << ' ' << e.second + 1 << '\n';
}
int res = 0;
for(int i = 0; i < n; i++)
res += abs(deg[i]);
assert(res == incovenience);
}
return 0;
}
```

## Tester's Code

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector<int> uf(n);
iota(uf.begin(), uf.end(), 0);
vector<vector<pair<int,int>>> indep(n), spanning(n);
function<int(int)> find = [&](int x){
return x == uf[x] ? x : uf[x] = find(uf[x]);
};
auto merge = [&](vector<pair<int,int>> &a, vector<pair<int,int>> &b){
if(a.size() < b.size()){
for(auto & e : a) b.push_back(e);
swap(a, b);
} else {
for(auto & e : b) a.push_back(e);
}
b.clear();
};
auto join = [&](int u, int v){
int fu = find(u);
int fv = find(v);
if(fu == fv){
indep[fu].push_back({u, v});
} else {
spanning[fu].push_back({u, v});
merge(indep[fu], indep[fv]);
merge(spanning[fu], spanning[fv]);
uf[fv] = fu;
}
};
int incovenience = 0;
auto incov_join = [&](int u, int v){
u = find(u);
v = find(v);
if(indep[u].size() < indep[v].size()) swap(u, v);
if(indep[u].size() + indep[v].size() == 0){
incovenience += 2;
spanning[u].push_back({u, v});
merge(spanning[u], spanning[v]);
} else {
auto edge_u = indep[u].back(); indep[u].pop_back();
if (indep[v].empty()) {
auto edge_v = spanning[v].back(); spanning[v].pop_back();
spanning[u].push_back({edge_u.first, edge_v.first});
spanning[u].push_back({edge_u.second, edge_v.second});
} else {
auto edge_v = indep[v].back(); indep[v].pop_back();
spanning[u].push_back({edge_u.first, edge_v.first});
indep[u].push_back({edge_u.second, edge_v.second});
}
merge(spanning[u], spanning[v]);
merge(indep[u], indep[v]);
}
uf[v] = u;
};
vector<int> deg(n);
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
u--; v--;
join(u, v);
deg[u]++;
deg[v]++;
}
vector<pair<int,int>> comp;
vector<int> nodes;
for(int i = 0; i < n; i++) if(i == uf[i] && spanning[i].empty()) {
nodes.push_back(i);
}
for(int i = 0; i < n; i++) if(i == uf[i] && !spanning[i].empty()) {
comp.push_back({indep[i].size(), i});
}
if (comp.empty()) {
cout << (n - 1) * 2 << ' ' << n - 1 << '\n';
for(int i = 1; i < n; i++){
cout << nodes[0] + 1 << ' ' << nodes[i] + 1 << '\n';
}
continue;
}
sort(comp.rbegin(), comp.rend());
for(int i = 1; i < comp.size(); i++){
incov_join(comp[0].second, comp[i].second);
}
int root = find(comp[0].second);
while(indep[root].size() > 0 && nodes.size() >= 2){
auto edge_i = indep[root].back(); indep[root].pop_back();
int u = nodes.back(); nodes.pop_back();
int v = nodes.back(); nodes.pop_back();
spanning[root].push_back({u, edge_i.first});
spanning[root].push_back({v, edge_i.second});
incovenience += 2;
}
if(nodes.size()){
spanning[root].push_back({root, nodes.back()});
incovenience += 2;
}
merge(spanning[root], indep[root]);
cout << incovenience << ' ' << spanning[root].size() << '\n';
for(auto e : spanning[root]){
deg[e.first]--;
deg[e.second]--;
assert(e.first != e.second);
cout << e.first + 1 << ' ' << e.second + 1 << '\n';
}
int res = 0;
for(int i = 0; i < n; i++)
res += abs(deg[i]);
assert(res == incovenience);
}
return 0;
}
```

## Editorialist's Code

```
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ld long double
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define vv vector
#define endl '\n'
using namespace std;
const int MAXN = 100*1000 + 5;
struct DSU{
int parent[MAXN];
vv<ii> extraEdge[MAXN];
DSU(){
FOR(i,MAXN)parent[i] = i;
}
int find(int a){
if(parent[a] != a)parent[a] = find(parent[a]);
return parent[a];
}
bool isSame(int a,int b){
return find(a) == find(b);
}
void merge(int a,int b){
if(isSame(a,b)){
int pa = find(a);
extraEdge[pa].pb({a,b});
}else{
int pa = find(a);
int pb = find(b);
if(extraEdge[pa].size() > extraEdge[pb].size()){
parent[pb] = pa;
for(auto e: extraEdge[pb])extraEdge[pa].pb(e);
}else{
parent[pa] = pb;
for(auto e: extraEdge[pa])extraEdge[pb].pb(e);
}
}
}
};
multiset<int> g[MAXN];
void solve(){
DSU dsu;
int n,m;
cin >> n >> m;
FOR(i,n)g[i].clear();
FOR(i,m){
int a,b;
cin >> a >> b;
a--;b--;
dsu.merge(a,b);
g[a].insert(b);
g[b].insert(a);
}
vi allRootsNotTree;
vi allRootsTree;
FOR(i,n){
if(dsu.find(i) == i){
if(dsu.extraEdge[i].empty())allRootsTree.pb(i);
else allRootsNotTree.pb(i);
}
}
vv<ii> allExtraEdges;
vv<ii> newEdges;
int s = allRootsNotTree.size();
if(s > 1){
FOR(i,s){
ii ed = dsu.extraEdge[allRootsNotTree[i]].back();
ii edn = dsu.extraEdge[allRootsNotTree[(i+1)%s]].back();
//cout << ed.ff << " " << ed.ss << endl;
//cout << ed.ff << " " << ed.ss << endl;
g[ed.ff].erase(g[ed.ff].find(ed.ss));
g[ed.ss].erase(g[ed.ss].find(ed.ff));
g[ed.ss].insert(edn.ff);
g[edn.ff].insert(ed.ss);
if(i == 0)allExtraEdges.pb({edn.ff,ed.ss});
}
}
if(s > 1){
FOR(i,s)dsu.extraEdge[allRootsNotTree[i]].pop_back(); // since all these were already used.
}
FOR(i,s){
for(auto e : dsu.extraEdge[allRootsNotTree[i]]){
allExtraEdges.pb(e);
}
}
int x = 0;
vi listOf1Nodes;
while(!allExtraEdges.empty()){
auto e = allExtraEdges.back();
if(allRootsTree.empty())break;
int item = allRootsTree.back();allRootsTree.pop_back();
if(g[item].empty())listOf1Nodes.pb(item);
else{
int nitem = *(g[item].begin());
g[item].erase(g[item].find(nitem));
g[e.ff].erase(g[e.ff].find(e.ss));
g[e.ss].erase(g[e.ss].find(e.ff));
g[nitem].erase(g[nitem].find(item));
g[item].insert(e.ff);
g[e.ff].insert(item);
g[nitem].insert(e.ss);
g[e.ss].insert(nitem);
allExtraEdges.pop_back();
}
}
for(auto e : listOf1Nodes)allRootsTree.pb(e);
for(auto e : allExtraEdges){
if(allRootsTree.size() == 0){
break;
}
if(allRootsTree.size() == 1){
g[e.ff].erase(g[e.ff].find(e.ss));
g[e.ss].erase(g[e.ss].find(e.ff));
int root1 = allRootsTree.back();allRootsTree.pop_back();
g[e.ff].insert(root1);
g[e.ss].insert(root1);
g[root1].insert(e.ff);
g[root1].insert(e.ss);
x+=2;
break;
}
g[e.ff].erase(g[e.ff].find(e.ss));
g[e.ss].erase(g[e.ss].find(e.ff));
int root1 = allRootsTree.back();allRootsTree.pop_back();
int root2 = allRootsTree.back();allRootsTree.pop_back();
g[e.ff].insert(root1);
g[e.ss].insert(root2);
g[root1].insert(e.ff);
g[root2].insert(e.ss);
x+=2;
}
//cout << "SSGDFg" << endl;
int root1;
if(allRootsNotTree.empty())root1 = allRootsTree[0];
else root1 = allRootsNotTree[0];
for(auto e : allRootsTree){
if(allRootsNotTree.empty() and e == allRootsTree[0])continue;
x += 2;
g[e].insert(root1);
g[root1].insert(e);
}
vv<ii> allEdges;
FOR(i,n){
for(auto e: g[i]){
if(i < e){
allEdges.pb({i,e});
}
}
}
cout << x << " " << allEdges.size() << endl;
for(auto e: allEdges){
cout << e.ff+1 << " " << e.ss+1 << endl;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)solve();
return 0;
}
```

Please give me suggestions if anything is unclear so that I can improve. Thanks