RPLA - Answer the boss! - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : RPLA

👉 Hint : 1D DP

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

vector<int> adj[1001];

bool visited[1001];
int dpRank[1001];
vector<pair<int,int> >mp;

bool comp(pair<int,int> a,pair<int,int> b)
{
    if(a.first!=b.first)
        return a.first<b.first;
    return a.second<b.second;    
}

void CalcRank(int v)
{
	visited[v]=1;
	for(auto it=adj[v].begin();it!=adj[v].end();it++)
	{
		if(dpRank[*it]==-1)
			CalcRank(*it);
		dpRank[v]=max(dpRank[v],1+dpRank[*it]);
	}
	if(dpRank[v]==-1)
		dpRank[v]=1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin>>t;
	for(int k=1;k<=t;k++)
	{
		int n,r,a,b;
		cin>>n>>r;
		mp.clear();
		memset(dpRank,-1,sizeof(dpRank));
		memset(visited,0,sizeof(visited));
		for(int i=0;i<=n;i++)
			adj[i].clear();
		while(r--)
		{
			cin>>a>>b;
			adj[a].push_back(b);
		}
		for(int i=0;i<n;i++)
			if(!visited[i])
				CalcRank(i);
		for(int i=0;i<n;i++)
			mp.push_back(make_pair(dpRank[i],i));
		sort(mp.begin(),mp.end(),comp);	
		cout<<"Scenario #"<<k<<":"<<endl;	
		for(auto it =mp.begin();it!=mp.end();it++)
		    cout<<it->first<<" "<<it->second<<endl;
	}
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.