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
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Panda and Destruction problem solution

YASH PAL, 31 July 2024
In this HackerEarth Panda and Destruction problem solution There is a country which is infected by virus. It has many cities and some cities are connected to other cities. In order to prevent virus from spreading Panda plans on destroying the connection between all the cities. Panda has got a power called pimogio. Using this power he can destroy any city, which results in destruction of all connections from this city. For destroying one city, Panda requires one unit pimogio power. Panda’s final aim is to isolate all the cities. In order to do so, Panda follows a simple approach, he keeps on destroying the city with most number of connections in it at that moment.
Since Panda is weak in calculation, please help him in finding out the units of pimogio power required by him to achieve his aim. There cannot be multiple connections between two cities i.e. two cities can have only one road connected to them.
HackerEarth Panda and Destruction problem solution

HackerEarth Panda and Destruction problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(i= a ; i < b ; ++i)
#define rep(i,n) FOR(i,0,n)
#define INF INT_MAX
#define ALL(x) x.begin(),x.end()
#define LET(x,a) __typeof(a) x(a)
#define IFOR(i,a,b) for(LET(i,a);i!=(b);++i)
#define EACH(it,v) IFOR(it,v.begin(),v.end())
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair
#define fill(x,v) memset(x,v,sizeof(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define si(n) scanf("%d",&n)
#define pi(n) printf("%d ",n)
#define pd(n) printf("%lf ",n);
#define pdl(n) printf("%lfn",n);
#define pin(n) printf("%dn",n)
#define pln(n) printf("%lldn",n)
#define pl(n) printf("%lld ",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define scan(v,n) vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
#define mod (int)(1e9 + 7)
#define ll long long int
#define TRACE

#ifdef TRACE
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif
#define F first
#define S second
ll modpow(ll a,ll n,ll temp){ll res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;}
vector<int> arr[100005];
int deg[100005];
set<pair<int,int> > stit;
int main()
{
int n,m,ans=0,i,a,b,node,sz,i1;
pair<int,int> calc;
si(n);
si(m);
rep(i,m)
{
si(a);
si(b);
deg[a]++;
deg[b]++;
arr[a].pb(b);
arr[b].pb(a);
}
FOR(i,1,n+1)
{
if(deg[i]!=0)
stit.insert(mp(deg[i], i));
}
while(!(stit.empty()))
{
calc=*stit.rbegin();
stit.erase(stit.find(calc));
node=calc.S;
sz=arr[node].size();
ans++;
rep(i,sz)
{
i1=arr[node][i];
if(stit.find(mp(deg[i1],i1))!=stit.end())
{
stit.erase(mp(deg[i1],i1));
deg[i1]--;
if(deg[i1]>0)
stit.insert(mp(deg[i1],i1));
}
}
}
pin(ans);
return 0;
}

Second solution

#include <cstdio>
#include <set>
#include <algorithm>
#include <cassert>
#include <vector>
#include <cstdlib>

using namespace std;

#define MAXN 100000
#define MAXM 300000

int degree[MAXN+1];
vector<int> G[MAXN+1];
int N, M;

set<pair<int, int> > edges;

int solve(){
int ans = 0;
set<pair<int, int> > S;

for(int i=0;i<N;i++)
S.insert(make_pair(-degree[i], i));
while(!S.empty()){
pair<int, int> top = *S.begin();
int deg = - top.first;
int node = top.second;
//printf("%d %dn", deg, node);

S.erase(S.begin());
degree[node] = 0;
for(int i=0;i<G[node].size(); i++){
if(degree[G[node][i]] > 0){
//this node is still alive, destroy the edge
pair<int, int> el = *S.find(make_pair(-degree[G[node][i]], G[node][i]));
S.erase(S.find(make_pair(-degree[G[node][i]], G[node][i])));
degree[G[node][i]]--;
if(degree[G[node][i]] > 0)
S.insert(make_pair(-degree[G[node][i]], G[node][i]));

}
}
ans++;

}
return ans;
}
int main(){
for(int i=0; i<=MAXN;i++)
degree[i] = 0;

int a, b, c;
scanf("%d %d", &N, &M);
assert(N>0 and N<=MAXN);
assert(M>0 and M<=MAXM);
for(int i=0;i<M;i++){
scanf("%d %d", &a, &b);
assert(a>0 and a<=N);
assert(b>0 and b<=N);
a--, b--;
G[a].push_back(b);
G[b].push_back(a);
degree[a]++;
degree[b]++;

assert(a!=b);
if(b<a){
c = a;
a = b;
b = c;
}
if(edges.find(make_pair(a, b)) != edges.end()){
assert(false);
}
edges.insert(make_pair(a, b));
}
printf("%dn", solve());
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

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