一、思路分析
1、不停的接收结点关系，创建有向图，A->B有边表示 A<B
2、每进入一个结点关系后，判断现在的有向图是否有环，有环就是冲突，提示并退出。判断是否有环可以用拓扑排序，
判断方法是：只要入队（或者出队）的次数不等于节点的个数，就说明有环，有环就是存在矛盾的。
3、在无环的情况下，找到入度为0的点，就是起始点，然后从起始点出发，bfs，看看能不能走出n步，如果能，就是完成了排序工作
二、理解与感悟
1、拓扑排序可以判断有没有环。
2、有环就是表示有循环比大小，就是有冲突。
3、拓扑排序要不断修改入度数组，如果入度数组需要不断建边继续使用，需要复制出来一份才能边建边、边检查拓扑序。
4、单个字符转字符串的办法最好用的是常量字符串(ABCDEFGHIJKLMNOPQRSTUVWXYZ)的(substr),其它的花里胡哨的不好用，背模板吧。
三、邻接表解法
#include <bits/stdc++.h>
using namespace std;
const int N = 30; //26个结点是极限
int in[N]; //入度数组
int tmp[N]; //入度临时操作数组
int n; //表示需要排序的元素数量
int m; //表示将给出的形如 A<B 的关系的数量
bool st[N]; //是否使用过
//实在想不出好主意了,用数字转为字符，再拼接到字符串，现在看来最好的办法就是写成一个常量字符串，然后substr去截取
string chr = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct Node {
int n;
string path;
};
//邻接表
vector<int> edge[N];
//拓扑排序，检查是否存在环，有环就是存在矛盾
bool topSort() {
//清空状态数组
memset(st, 0, sizeof st);
queue<int> q; //拓扑排序用的队列
int sum = 0;//入队列数量
//判断现在是不是有环，有环则退出。入度为0的结点入队列，进行拓扑排序
for (int j = 1; j <= n; j++) if (!tmp[j]) q.push(j);
//拓扑排序
while (!q.empty()) {
int u = q.front();
q.pop();
sum++;
//不是环中结点
st[u] = true;
//遍历每条出边
for(auto c:edge[u]){
if (!--tmp[c]) q.push(c);//在删除掉当前结点带来的入度后，是不是入度为0了，如果是将点y入队列
}
}
//存在没进过队列的结点，存在表示有环。
return sum < n;
}
int main() {
//读入结点数和边数
cin >> n >> m;
//读入关系，建图，边建图边判断
for (int i = 1; i <= m; i++) {
string input;
cin >> input;
char x = input[0], y = input[2];//input[1]='<' 这个是死的，没用
//建图
int a = x - 'A' + 1, b = y - 'A' + 1;
edge[a].push_back(b);//建立单边有向图,描述a<b
in[b]++; //入度数组++
/*****下面的代码是拓扑排序的内容*******************************************************/
//入度数组复制出来一份,因为拓扑排序需要不断的更改入度数组值，后面还需要原始的入度数组，所以需要复制出来一份。
memcpy(tmp, in, sizeof in);
bool existCircle = topSort();
if (existCircle) {
printf("Inconsistency found after %d relations.", i);
exit(0);
}
/*****拓扑排序结束*********************************************************************/
//到这里应该是无环
//从入度为0的点出发，bfs看看是不是能走完n步，走完说明可以确定所有结点的大小关系，确定了就结束
int cnt = 0;
int startNode;
for (int j = 1; j <= n; j++) if (!in[j]) startNode = j, cnt++;
if (cnt > 1) continue; //存在两个及以上入度为零的点，是无法确定先后顺序的,需要继续读入关系数据
//从startNode出发，看看能不能走出去n轮，如果能，就是可以确定所有结点的顺序，如果不能，就需要继续录入关系才能确定
string path;
queue<Node> q;
q.push({startNode, chr.substr(startNode - 1, 1)});
//清空状态数组，准备再战!
memset(st, 0, sizeof st);
while (!q.empty()) {
Node u = q.front();
q.pop();
st[u.n] = true;
if (u.path.size() > path.size())path = u.path;
//遍历每条出边
for (auto c:edge[u.n])
q.push({c, u.path + chr.substr(c - 1, 1)});
}
//如果还存在没访问到的结点，那么就是无法完成排序,需要继续录入关系
if (path.size() < n) continue;
//输出路径
printf("Sorted sequence determined after %d relations: %s.", i, path.c_str());
exit(0);
}
//到达这里说明最终还没有确定下来所有结点关系，提示无法确定。
printf("Sorted sequence cannot be determined.");
return 0;
}
四、链式前向星解法
#include <bits/stdc++.h>
using namespace std;
const int N = 30; //26个结点是极限
const int M = 610; //600条边是极限
int in[N]; //入度数组
int tmp[N]; //入度临时操作数组
int n; //表示需要排序的元素数量
int m; //表示将给出的形如 A<B 的关系的数量
bool st[N]; //是否使用过
//实在想不出好主意了,用数字转为字符，再拼接到字符串，现在看来最好的办法就是写成一个常量字符串，然后substr去截取
string chr = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct Node {
int n;
string path;
};
//链式前向星
int idx;
int head[N]; //链表头数组
struct Edge {
int to, next;
} edge[M];
//从u向v连一条边，本题无权值概念,头插法
void add(int u, int v) {
edge[++idx].to = v;
edge[idx].next = head[u];
head[u] = idx;
}
//拓扑排序，检查是否存在环，有环就是存在矛盾
bool topSort() {
//清空状态数组
memset(st, 0, sizeof st);
queue<int> q; //拓扑排序用的队列
int sum = 0;//入队列数量
//判断现在是不是有环，有环则退出。入度为0的结点入队列，进行拓扑排序
for (int j = 1; j <= n; j++) if (!tmp[j]) q.push(j);
//拓扑排序
while (!q.empty()) {
int u = q.front();
q.pop();
sum++;
//不是环中结点
st[u] = true;
//遍历每条出边
for (int j = head[u]; j; j = edge[j].next) {
int y = edge[j].to;
if (!--tmp[y]) q.push(y);//在删除掉当前结点带来的入度后，是不是入度为0了，如果是将点y入队列
}
}
//存在没进过队列的结点，存在表示有环。
return sum < n;
}
int main() {
//读入结点数和边数
cin >> n >> m;
//读入关系，建图，边建图边判断
for (int i = 1; i <= m; i++) {
string input;
cin >> input;
char x = input[0], y = input[2];//input[1]='<' 这个是死的，没用
//建图
int a = x - 'A' + 1, b = y - 'A' + 1;
add(a, b); //建立单边有向图,描述a<b
in[b]++; //入度数组++
/*****下面的代码是拓扑排序的内容*******************************************************/
//入度数组复制出来一份,因为拓扑排序需要不断的更改入度数组值，后面还需要原始的入度数组，所以需要复制出来一份。
memcpy(tmp, in, sizeof in);
bool existCircle = topSort();
if (existCircle) {
printf("Inconsistency found after %d relations.", i);
exit(0);
}
/*****拓扑排序结束*********************************************************************/
//到这里应该是无环
//从入度为0的点出发，bfs看看是不是能走完n步，走完说明可以确定所有结点的大小关系，确定了就结束
int cnt = 0;
int startNode;
for (int j = 1; j <= n; j++) if (!in[j]) startNode = j, cnt++;
if (cnt > 1) continue; //存在两个及以上入度为零的点，是无法确定先后顺序的,需要继续读入关系数据
//从startNode出发，看看能不能走出去n轮，如果能，就是可以确定所有结点的顺序，如果不能，就需要继续录入关系才能确定
string path;
queue<Node> q;
q.push({startNode, chr.substr(startNode - 1, 1)});
//清空状态数组，准备再战!
memset(st, 0, sizeof st);
while (!q.empty()) {
Node u = q.front();
q.pop();
st[u.n] = true;
if (u.path.size() > path.size())path = u.path;
//遍历每条出边
for (int j = head[u.n]; j; j = edge[j].next) {
int y = edge[j].to;
q.push({y, u.path + chr.substr(y - 1, 1)});
}
}
//如果还存在没访问到的结点，那么就是无法完成排序,需要继续录入关系
if (path.size() < n) continue;
//输出路径
printf("Sorted sequence determined after %d relations: %s.", i, path.c_str());
exit(0);
}
//到达这里说明最终还没有确定下来所有结点关系，提示无法确定。
printf("Sorted sequence cannot be determined.");
return 0;
}