HackerEarth Kingdom Of Monkeys problem solution

In this HackerEarth Kingdom Of Monkeys problem solution This is the story in Zimbo, the kingdom officially made for monkeys. Our Code Monk visited Zimbo and declared open a challenge in the kingdom, thus spoke to all the monkeys :

You all have to make teams and go on a hunt for Bananas. The team that returns with the highest number of Bananas will be rewarded with as many gold coins as the number of Bananas with them. May the force be with you!

Given there are N monkeys in the kingdom. Each monkey who wants to team up with another monkey has to perform a ritual. Given total M rituals are performed. Each ritual teams up two monkeys. If Monkeys A and B teamed up and Monkeys B and C teamed up, then Monkeys A and C are also in the same team.

You are given an array A where Ai is the number of bananas i’th monkey gathers.

Find out the number of gold coins that our Monk should set aside for the prize.

HackerEarth Kingdom Of Monkeys problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define inf 1e9

#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define f first
#define s second
#define rep(i,n) for(int i=0;i<n;i++)                                                             

int visi[200000];
ll int arr[200000];
std::vector< vector<int> > gr;
ll int te=0;                  
void dfs( int no )            
{     
  //cout<<no<<" ";        
  visi[no]=1;
  te+=arr[no];
  int i;
  for(i=0;i<gr[no].size();i++)
  {
    int tn=gr[no][i];
    if(!visi[tn])
    {
           dfs(tn);
    }
  }
}
int main()
{
  
//  ios::sync_with_stdio(false);
  int t;
  cin>>t;
  while(t--)
  {
    int i,j,k,n,m;
    cin>>n>>m;
    gr.clear();
    gr.resize(n+5);
    assert(1<=n && n<=100000);
    assert(1<=m && m<=100000);
    rep(i,m)
    {
        cin>>j>>k;
        j--;
        k--;
        gr[j].pb(k);
        gr[k].pb(j);
    }
    rep(i,n){
    cin>>arr[i];
    assert(arr[i]>=0 && arr[i]<=1000000000000);
  }
    memset(visi,0,sizeof(visi));
    ll int ans=0;
    rep(i,n)
    {
      if(visi[i]==0)
      {
        te=0;
        dfs(i);
        ans=max(te,ans);
      }
      else
        continue;
    }
    cout<<ans;
    if(t>0)cout<<"n";
  }
  return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define all(x) x.begin(),x.end()
#define mset(x,v) memset(x, v, sizeof(x))
#define sz(x) (int)x.size()

vi adj[100005];
ll v[100005];
int vis[100005];

ll dfs(int u)
{
    int i;
    ll sum = v[u];
    vis[u] = 1;
    for(i=0;i<sz(adj[i]);i++)
    {
        int v = adj[u][i];
        if(!vis[v])
        {
            dbg(v);
            sum += dfs(v);
        }
    }
    return sum;
}

int main()
{
    int t;
    scanf("%d",&t);
    assert(1 <= t && t <= 100);
    while(t--)
    {
        int n,m,i;
        scanf("%d%d",&n,&m);
        assert(1 <= n && n <= 100000);
        assert(1 <= m && m <= 100000);
        for(i=1;i<=n;i++)
        {
            vis[i] = 1;
            adj[i].clear();
        }
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            adj[u].pb(v);
            adj[v].pb(u);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&v[i]);
            assert(0 <= v[i] && v[i] <= (ll)1e12);
        }
        ll ans = 0;
        for(i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                ans = max(ans,dfs(i));
                dbg(ans);
            }
        }
        printf("%lldn",ans);
    }
    return 0;
}

coding problems solutions