Educational DP Contest G - Longest Path (dp,拓扑排序)

题意:给你一张DAG,求图中的最长路径.
题解:用拓扑排序一个点一个点的拿掉,然后dp记录步数即可.

代码:

int n,m;

int a,b;

vector<int> v[N];

int in[N];

int dp[N];

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	n=read();

	m=read();

	for(int i=1;i<=m;++i){

		a=read();

		b=read();

		v[a].pb(b);

		in[b]++;

	}

	queue<int> q;

	for(int i=1;i<=n;++i){

		if(!in[i]) q.push(i);

	}

	while(!q.empty()){

		int now=q.front();

		q.pop();

		for(auto w:v[now]){

			in[w]--;

			if(!in[w]){

				q.push(w);

				dp[w]=dp[now]+1;

			}

		}

	}

	int ans=0;

	for(int i=1;i<=n;++i){

		ans=max(ans,dp[i]);

	}

	printf("%d\n",ans);

    return 0;

}

巴特西

Educational DP Contest G - Longest Path (dp,拓扑排序)

最新文章

热门文章