[数据结构与算法]拓扑排序（c++）

题目描述

以邻接矩阵给出一张以整数为结点的有向图，其中0表示不是相邻结点，1表示两个结点相连且由当前结点为初始点。利用拓扑排序判断图中是否有环，若有输出YES没有输出NO,

输入

结点数
邻接矩阵

输出

YES/NO

样例输入

3
0 1 0
1 0 1
1 0 0

样例输出

YES

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

int num;
int** edge;

void Tp() {
	int* in = new int[num];//入度
	for (int i = 0; i < num; i++) in[i] = 0;

	for (int i = 0; i < num; i++){//找每个顶点的入度
		for (int j = 0; j < num; j++) {
			if (edge[i][j] != 0) in[j]++;
		}
	}

	int temp;
	int flag = 1;
	for (int i = 0; i < num; i++) {
		int count = 0;

		for (int j = 0; j < num; j++) {
			if (in[j] == 0) {//找到一个入度为0的
				temp = j;
				in[j]--;//相当于从图中删掉
				break;
			}
			else
				count++;
		}
		if (count == num) {
			flag = 0;
			cout << "YES" << endl;
			break;
		}
		for (int j = 0; j < num; j++) {//与入度为0的点相连的点的入度减一
			if (edge[temp][j] != 0)
				in[j]--;
		}
	}
	if (flag) cout << "NO" << endl;
}

int main() {
	cin >> num;
	edge = new int* [num];
	for (int i = 0; i < num; i++)
		edge[i] = new int[num];

	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			cin >> edge[i][j];

	Tp();

}