【数据结构OJ】【图论】图综合练习--拓扑排序

题目描述

已知有向图，顶点从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;
}