海南省城乡建设部网站首页,魅影传说网页游戏开服表,开平做网站,生成小程序题目描述 已知有向图#xff0c;顶点从0开始编号#xff0c;求它的求拓扑有序序列。 拓扑排序算法#xff1a;给出有向图邻接矩阵 1.逐列扫描矩阵#xff0c;找出入度为0且编号最小的顶点v
2.输出v#xff0c;并标识v已访问
3.把矩阵第v行全清0
重复上述步骤#xff0…题目描述 已知有向图顶点从0开始编号求它的求拓扑有序序列。 拓扑排序算法给出有向图邻接矩阵 1.逐列扫描矩阵找出入度为0且编号最小的顶点v
2.输出v并标识v已访问
3.把矩阵第v行全清0
重复上述步骤直到所有顶点输出为止 --程序要求--
若使用C只能include一个头文件iostream若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件不看代码作0分处理
不允许使用第三方对象或函数实现本题的要求
输入 第一行输入一个整数t表示有t个有向图
第二行输入n表示图有n个顶点
第三行起输入n行整数表示图对应的邻接矩阵
以此类推输入下一个图的顶点数和邻接矩阵
输出 每行输出一个图的拓扑有序序列
IO模式
本题IO模式为标准输入/输出(Standard IO)你需要从标准输入流中读入数据并将答案输出至标准输出流中。
输入样例
2 5 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 输出样例
0 1 3 2 4 4 6 5 1 3 2 0
AC代码
#include iostream
using namespace std;int main() {int t;cin t;while (t--) {int n;cin n;int a[n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {cin a[i][j];}}int rudu[n];for (int i 0; i n; i) {rudu[i] 0;}for (int i 0; i n; i) {for (int j 0; j n; j) {if (a[j][i] 1) {rudu[i];}}}int tag[n];for (int i 0; i n; i) {tag[i] 0;}int sum 0;while (1) {for (int j 0; j n; j) {if (rudu[j] 0 tag[j] 0) {cout j ;tag[j] 1;for (int i 0; i n; i) {if (a[j][i] 1) {rudu[i]--;}}sum;break;}}if (sum n) {cout endl;break;}}}
return 0;
}
