HackerEarth So NP problem solution YASH PAL, 31 July 2024 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