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

coding problems solutions