# HackerEarth So NP problem solution

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.

`#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';}`