题库 信息学奥赛题库 题目列表 (最长路径)给定一个有向无环图,每条边长度为 1,求...
组合题

(最长路径)给定一个有向无环图,每条边长度为 1,求图中的最长路径长度。

(第五空 2 分,其余 3 分) 输入:第一行是结点数 n(不超过 100)和边数 m,接下来 m

行,每行两个整数 a, b,表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到(n-1)。

输出:最长路径长度。 提示:先进行拓扑排序,然后按照拓扑序计算最长路径。

#include<iostream>
using namespace std;
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;
		(1);
	}
	tail = 0;
	for (i = 0; i < n; i++)
		if ((2)) {
			queue[tail] = i;
			tail++;
		}
	head = 0;
	while (tail < n - 1) {
		for (i = 0; i < n; i++)
			if (graph[queue[head]][i] == 1) {
				(3);
				if (degree[i] == 0) {
					queue[tail] = i;
					tail++;
				}
			}
		(4);
	}
	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 ((5))
			ans = len[a];
	}
	cout << ans << endl;
	return 0;
}
第 1 题 填空
第 2 题 填空
第 3 题 填空
第 4 题 填空
第 5 题 填空
题目信息
阅读程序 2017年 初赛
-
正确率
0
评论
29
点击
QQ
微信