At Coder Educational DP-G | DP Series(Episode-9)

 Problem Description here

Problem: এই প্রব্লেমে আমাদের মূলত একটি DAG দেয়া থাকবে। Longest Directed Path এর লেন্থ বের করতে হবে। 

Solution:

এই প্রব্লেমে আমরা মূলত প্রতিটি নোড থেকে DFS ছেড়ে দেখবো যে কত Depth এ যাওয়া সম্ভব। এভাবে প্রতিটি নোডের জন্য প্রাপ্ত ভ্যালু নিয়ে এন্সার ম্যাক্সিমাইজ করবো। 

	#include<bits/stdc++.h>
	using namespace std;
	vector<int>graph[100005];
	int n,m,dp[100005];
	int fun(int u)
	{
	if(graph[u].size() == 0)
	return 0;
	if(dp[u] != -1)
	return dp[u];
	int ret1=0,opt=0;
	for(int v : graph[u]){
	ret1 = 1+fun(v);
	opt = max(opt,ret1);
	}
	return dp[u]=opt;
	}
	int main()
	{
	int i,j,k,u,v,ans=0,x;
	memset(dp , -1 , sizeof(dp));
	cin>>n>>m;
	for(i=1;i<=m;i++){
	cin>>u>>v;
	graph[u].push_back(v);
	}
	for(i=1;i<=n;i++){
	x = fun(i);
	ans = max(ans,x);
	}
	cout<<ans<<endl;
	return 0;
	}

view raw Episode-9.1.cpp hosted with ❤ by GitHub

Next Episode

Happy Coding