最长路径:给定一个有向五环图,每条边长度为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;
}