In this HackerEarth Big P and Punishment problem solution Big P has become a Physical Education teacher at Hack International School.

Today, the students of class XII have been very undisciplined and he decides to punish them all.

He makes all of the N student (numbered 1 to N ) to stand in a line and asks them to sit down on their knees.

Students know that Big P is a very cruel and sadistic person and students start to sit down themselves when they see a friend sit down.

However, there are always some students who do not follow the trend. Now when Big P sees that happen , he slaps that student and makes him sit down. The same process as above is followed and is stopped when any - one student in the line refuses to sit down by himself.

Given the students that Big P slaps to make them sit down , you need to tell the total no. of students who sat down in that line.


HackerEarth Big P and Punishment problem solution


HackerEarth Big P and Punishment problem solution.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define D(x) cout << #x " is " << x << endl
using namespace std;
const int N = 10009;

vector<int> g[N];
bool sat[N];
int ans;

void sit(int u){
if (sat[u]) return;

ans++;
sat[u] = true;

for (int i=0; i<g[u].size(); ++i) sit(g[u][i]);
}

int main()
{

int c;
for (cin >> c; c--; cout << ans << endl)
{
int n, m, l;
cin>>n>>m>>l;
for (int i=0; i<=n;i++)
{
g[i].clear();
sat[i] = false;
}
while(m--)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
}

ans = 0;
while (l--)
{
int u;
cin >> u;
sit(u);
}
}

return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<vector<int> > adj;

void dfs(int idx,bool *visited){

visited[idx]=1;

for(vector<int> :: iterator it=adj[idx].begin();it!=adj[idx].end();++it)
{
if(visited[*it]==false)
dfs(*it,visited);
}
}
int main(){

int t;
cin>>t;
while(t--){
int n,f,s;
cin>>n>>f>>s;
adj.resize(n);
for(int i=0;i<f;i++){
int a,b;
cin>>a>>b;
adj[a-1].pb(b-1);
}
bool visited[n];
memset(visited,0,sizeof(visited));
for(int i=0;i<s;i++){
int idx;
cin>>idx;
dfs(idx,visited);
}
int count=0;
for(int i=0;i<n;i++) if(visited[i]) count++;

cout<<count<<endl;
}
return 0;
}