不是VIP会员,不能显示答案

题目解答

题目:
最长路径:给定一个有向五环图,每条边长度为1,求图中的最长路径长度。(第五空 2 分,其余 3分)
输入:第一行是结点数n(不超过100)和边数m,接下来m行,每行两个整数a,b,表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。
输出:最长路径长度。
提示:先进行拓扑排序,然后按照拓扑排序计算最长路径。
#include<iostream>
using namespacestd;
int n, m, i, j,a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100];     // 记录每个结点的入度
int len[100];       // 记录以各结点为终点的最长路径长度
int queue[100];    // 存放拓扑排序结果
int main() {
	cin >> n >> m;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			graph[i][j]= 0;
	for (i = 0; i < n; i++)
		degree[i] =0;
	for (i = 0; i < m; i++) {
		cin>> a >>b;
		graph[a][b]= 1;
		 degree[b]++ ;
	}
	tail = 0;
	for (i = 0; i < n; i++)
		if ( degree[i]==0 ) {
			queue[tail]= i;
			tail++;
		}
	head = 0;
	while (tail < n-1) {
		for (i = 0; i < n; i++)
			if(graph[queue[head]] [i] == 1) {
				 degree[i]-- ;
				if(degree[i] == 0) {
					queue[tail]= i;
					tail++;
				}
			}
		head++ ;
	}
	ans = 0;
	for (i = 0; i < n; i++) {
		a = queue[i];
		len[a] = 1;
		for (j = 0; j < n; j++)
			if(graph[j][a] == 1 && len[j] + 1 >len[a])
				len[a]= len[j] + 1;
		if (ans<len[a])
			ans= len[a];
	}
	cout << ans << endl;
	return 0;
}
考点: 0
分析:
解答: 每一步都非常明确,第一问是更新入度,第二问是将入度为0的入队,第三问删边更新入度,第四问头指针后移,第五问更新答案,注意求的是最长路
评论:
老师: 0