第九个测试点 已判断出是因为错误将 情况1 判断为 情况3。

蒟蒻想法

先判断图是否连通 如果连通

使用入度数组拓扑排序

如果没有拓扑序就终止 否则输出情况1

最后如果两种情况都没出现输出情况3

求助各位神犇

是思路错了还是代码有问题Orz

代码有简单注释

#include <iostream>
#include <string>
#include <list>
#include <queue>
using namespace std;
struct point {
public:
	char bh;
	list<char>outside;
	void insert(char to) {this->outside.push_back(to);}
	bool isfind;
};
long long int thenumber = 0;
point a[27];
vector<char>letter;
queue<char>zero;
queue<char>que1;
queue<char>que2;
int zeropath[27];
int n, m;
long long int num = 0;
bool bfs() {
	num = 0;
	que1.push('A' + n - 1);
	while (!que1.empty()) {
		while (!que1.empty()) {
			for (auto x : a[que1.front() - 'A'].outside)
				if(a[x-'A'].isfind==false)que2.push(x);
			a[que1.front() - 'A'].isfind = true;
			que1.pop();
		}
		while (!que2.empty()) {
			if(a[que2.front()-'A'].isfind==false)que1.push(que2.front());
			que2.pop();
		}
		++num;
	}
	return num >= n;
}//BFS判定图是否连通
void bfs2() {
	que1.push('A' + n - 1);
	while (!que1.empty()) {
		while (!que1.empty()) {
			for (auto x : a[que1.front() - 'A'].outside)
				if (a[x - 'A'].isfind == true)que2.push(x);
			a[que1.front() - 'A'].isfind = false;
			que1.pop();
		}
		while (!que2.empty()) {
			que1.push(que2.front());
			que2.pop();
		}
	}
}//这个BFS用来清场
bool tpsort() {
	letter.clear();
	for (int i = 0; i < n; i++)zeropath[i] = 0;
	for (int i = 0; i < n; i++)
		for (auto x : a[i].outside)
			++zeropath[x - 'A'];
	for (int i = 0; i < n; i++)
		if (zeropath[i] == 0)zero.push('A' + i);
	while (!zero.empty()) {
		for (auto x : a[zero.front() - 'A'].outside) {
			--zeropath[x - 'A'];
			if (zeropath[x - 'A'] == 0)zero.push(x);
		}
		letter.push_back(zero.front());
		zero.pop();
	}
	if (letter.size() < n)return false;
	else return true;
}//拓扑排序判定是否有环
int main() {
	char one, two, three;
	cin >> n >> m;
	for (int i = 0; i < n; i++)a[i].bh = 'A' + i;
	while (m--) {
		cin >> one >> three >> two;
		a[two - 'A'].insert(one);
		++thenumber;
		if (bfs()) {//如果图连通
			if (tpsort()) {//如果有拓扑序
				cout << "Sorted sequence determined after " << thenumber << " relations: ";
				for (int i = letter.size() - 1; i >= 0; i--)putchar(letter[i]); putchar('.');
				return 0;
			}
		}
		if (!tpsort()) {//如果没有拓扑序
			cout << "Inconsistency found after " << thenumber << " relations.";
			return 0;
		}
		bfs2();//清场
	}
	cout << "Sorted sequence cannot be determined.";//没有终止说明图不连通
	return 0;
}