HackerEarth Monk's birthday treat problem solution

In this HackerEarth Monk’s birthday treat problem solution Little Monk is an extremely miser person. He hates spending money on things, be it for his own good or bad. But this time his friends have caught up with him, and are demanding a huge birthday treat. But, Monk is… well, Monk.

He figured out that there is no way for him to save himself and his money now. So, he decided to treat as many friends as he can. But, he still thought that he could skip inviting those friends who don’t have any dependency. That is to say that, let’s say that he has N friends, and a friend Ai wouldn’t come to the party if Aj is not invited. But, it’s not necessary that the vice-versa is true.

Monk wants to invite minimum number of friends to celebrate his birthday party to save money – help Monk figure out the minimum number of friends he can invite while fulfilling their demands. He cannot have a party without any friend, so he HAS to take one friend with him, at least to celebrate his birthday, by the way.

HackerEarth Monk’s birthday treat problem solution.

#include<bits/stdc++.h>

using namespace std;
vector < vector < int > > graph;
int ans = 999999, cnt, n, d, a, b;
bool visited[1000];

void traverse(int a) {
  visited[a] = true;
  for(int i=0; i<graph[a].size();i++) {
    if(visited[graph[a][i]]==false) {
      cnt++;
      traverse(graph[a][i]);
    }
  }
}

int main() {
  graph.clear(); 
  scanf("%d%d",&n,&d);
  graph.resize(n);
  for(int i=0;i<d;i++) {
    scanf("%d%d",&a,&b);
    graph[a-1].push_back(b-1);
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<1001;j++)
      visited[j]=false;
    cnt =1;
    traverse(i);
    ans = min(cnt,ans);
  }
  printf("%dn",ans);
  return 0;
}

Second 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;                  
  ll  int dfs( int no )           
    {     
      //cout<<no<<" ";        
      visi[no]=1;
    ll  int an=1;
      int i;
      for(i=0;i<gr[no].size();i++)
      {
        int tn=gr[no][i];
        if(!visi[tn])
        {
               an+=dfs(tn);
        }
      }
      return an;
    }
    int main()
    {
        int i,j,k,n,m;
        cin>>n>>m;
        gr.clear();
        gr.resize(n+5);
        rep(i,m)
        {
            cin>>j>>k;
            j--;
            k--;
            gr[j].pb(k);
           // gr[k].pb(j);
        }
        memset(visi,0,sizeof(visi));
        ll int ans=999999999999;
        rep(i,n)
        {
          memset(visi,0,sizeof(visi));
          if(visi[i]==0  || 1)
          {
            te=999999;
            te=dfs(i);
            ans=min(te,ans);
          }
          else
            continue;
        }
        cout<<ans<<"n";
      return 0;
    }

coding problems solutions