In this HackerEarth So NP problem solution Once a upon time a problem setter offered a problem to Arpa. Like always Arpa said "eaaasy", but after a time Arpa said this problem is so NP.

Solve this problem to prove Arpa is always right and his first opinion is correct.

You are given a graph with n nodes and m edges.
Calculate maximum number of edges that can be removed from the graph so that it contains exactly k connected components.


HackerEarth So NP problem solution


HackerEarth So NP problem solution.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
int n, m, k;
vector<int> vc[maxn];
bool mark[maxn];

void dfs(int v){
mark[v] = 1;
for(int u: vc[v])
if(!mark[u])
dfs(u);
}

int main(){
cin >> n >> m >> k;
for(int u, v, i = 0; i < m; i++)
cin >> u >> v,
u--, v--,
vc[u].push_back(v),
vc[v].push_back(u);
int cnt = 0;
for(int i = 0; i < n; i++)
if(!mark[i])
dfs(i), cnt++;
if(cnt > k)
cout << -1;
else
cout << m - n + k;
}
Tester's Solution
// In the name of God.
// You are anything and We're nothing
// Ya ali!

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 17;
int n, m, k;
vector<int> g[maxn];
bool mark[maxn];
void dfs(int v){
mark[v] = 1;
for(auto u : g[v])
if(!mark[u])
dfs(u);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
for(int i = 0; i < m; i++){
int v, u;
cin >> v >> u;
v--, u--;
g[v].push_back(u);
g[u].push_back(v);
}
int cnt = 0;
for(int i = 0; i < n; i++)
if(!mark[i]){
cnt++;
dfs(i);
}
cout << (cnt > k ? -1 : m - (n - k)) << '\n';
}