HackerEarth Panda and Destruction problem solution

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.

#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("%lf\n",n);
#define pin(n) printf("%d\n",n)
#define pln(n) printf("%lld\n",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 %d\n", 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("%d\n", solve());
  return 0;
}