（代码在后面）

成绩排序

题目描述

期末考试结束后，Light_LE 想对他的 $n$ 个朋友的成绩（编号为 $1 \sim n$）进行排序。但是大家都不好意思把具体分数说出来，只会含蓄地告诉 Light_LE 他/她的分数比谁高。经过 Light_LE 的统计，他一共收集了 $m$ 组关系数据。请问 Light_LE 能否用这些仅有的关系数据给他朋友们的成绩进行排序呢？

输入格式

本题目含有多组测试数据

第一行输入一个字母 $T$ ，表示一共有 $T$ 组测试数据。

对于每组测试数据，请进行如下输入格式：

第一行输入两个数 $n, m$

接下来 $m$ 行，每行两个数 $a, b$ ，表示 $a$ 号朋友的分数比 $b$ 号朋友的分数高。

最后，为了方便阅读样例，输入一个 # 作为结束符号。（还不快谢谢出题人）

输出格式

输出共 $T$ 行，每行分别为问题的答案。如果能进行排序，就输出 YES。否则就输出 NO 。

样例 #1

样例输入 #1

3
5 4
1 2
2 3
3 4
4 5
#
5 5
2 5
5 1
2 1
4 2
1 3
#
5 7
1 2
2 4
3 4
5 4
2 5
3 2
1 3
#

样例输出 #1

YES
YES
YES

样例 #2

样例输入 #2

4
5 4
1 2
3 2
2 4
2 5
#
5 6
1 3
3 5
3 4
2 5
2 4
5 4
#
5 4
1 2
2 3
2 4
4 5
#
5 5
1 2
2 3
4 5
2 4
3 5
#

样例输出 #2

NO
NO
NO
NO

提示

样例 1 解释：

• 第一组测试数据：此时一共有 $5$ 个朋友、 $4$ 组关系数据。 1 号朋友的成绩比 2 号朋友的成绩高，2 号朋友的成绩比 3 号朋友的成绩高，3 号朋友的成绩比 4 号朋友的成绩高，4 号朋友的成绩比 5 号朋友的成绩高，那么可以将成绩排序为 $1 > 2 > 3 > 4 > 5$
• 第二组测试数据：正确的顺序为 $4 > 2 > 5 > 1 > 3$
• 第三组测试数据：正确的顺序为 $1 > 3 > 2 > 5 > 4$

测试数据保证：

1. 成绩不会重复。
2. 所有人的成绩都会参与高低比较。
3. 关系数据不会出现像 1 号朋友的成绩大于 2 号朋友的成绩，但 2 号朋友的成绩大于 1 号朋友的成绩的情况。

对于 $100 \%$ 的数据保证 $1 \le T \le 10, 2 \le n \le 10^4, 1 \le m \le 2 \times 10^4$

#include <bits/stdc++.h>
#define fin cin
#define fout cout

#define maxn 103
using namespace std;
int T, n, m;
vector<int> G1[maxn]/*正向存图*/, G2[maxn]/*反向存图*/;
queue<int> head/*头结点*/, tail/*尾节点*/;
bool dfs(int v, int cnt) {
	if (v == tail.front() && cnt == n) {
		return 1;
	}
	
	for (int i = 0; i < G1[v].size(); i++) {
		if (dfs(G1[v][i], cnt + 1)) {
			return 1;
		}
	}
	return 0;
}
int main() {
	//ifstream fin("sort.in");
	//ofstream fout("sort.out");
	ios::sync_with_stdio(0); fin.tie(0); fout.tie(0);

	fin >> T;
	while (T--) {
		// init
		memset(G1, 0, sizeof(G1));
		memset(G2, 0, sizeof(G2));
		while (head.size()) {
			head.pop();
		}
		while (tail.size()) {
			tail.pop();
		}
		
		fin >> n >> m;
		for (int i = 1; i <= m; i++) {
			int u, v;
			fin >> u >> v;
			G1[u].push_back(v);
			G2[v].push_back(u);
		}
		char c;
		fin >> c;
		
		for (int i = 1; i <= n; i++) {
			// 找出最前面的和最后面的节点
			if (G1[i].size() == 0) {
				tail.push(i);
			}
			if (G2[i].size() == 0) {
				head.push(i);
			}
		}
		
		// 特判 
		if (head.size() != 1 || tail.size() != 1) {
			fout << "NO" << endl;
			continue;
		}
		
		if (dfs(head.front(), 1)) {
			fout << "YES" << endl;
		}
		else {
			fout << "NO" << endl;
		}
	}
	return 0;
}