Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

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

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

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes