#include<bits/stdc++.h>
using namespace std;
int n, m; // n表示顶点数(字母数量),m表示边数(关系数量)
int graph[10010][10010]; // 邻接矩阵存储有向图,graph[i][j]=1表示i->j存在依赖
int degree[10010]; // 入度数组,记录每个顶点的入度
int now[10010]; // 当前处理时各顶点的入度(动态更新)
bool b[10010]; // 标记数组,b[i]=1表示顶点i已被加入序列
string ans; // 存储排序结果的字符串
// top函数——拓扑排序并返回排序状态
int top(){
ans = ""; // 清空上一轮排序结果
int f = 1; // f标记是否为唯一排序(f=1为唯一)
for(int i=1; i<=n; i++){ // 初始化
now[i] = degree[i];
b[i] = 0;
}
for(int o=0; o<n; o++){
int cnt = 0, minpos;
for(int i=1; i<=n; i++) //寻找入度为0的节点
if(b[i]==0 && now[i]==0) cnt++, minpos=i;
if(cnt == 0) return -1; // 存在环,无法排序
if(cnt >= 2) f = 0; // 不是唯一排序
ans += minpos+64; // 将字符加入结果
b[minpos] = 1; // 标记该顶点已处理
for(int j=1; j<=n; j++) // 更新相关顶点的入度
if(graph[minpos][j] == 1)
now[j]--;
}
return f; // 返回排序状态
}
int main(){
cin >> n >> m; // 输入顶点数和边数
getchar();
for(int i=1; i<=26; i++){// 初始化图和入度数组
for(int j=1; j<=26; j++)
graph[i][j] = 0;
degree[i] = 0;
}
int flag = 0; // 标记是否已找到答案或矛盾
for(int i=1; i<=m; i++){
string tmp;
getchar(); // 消耗换行符
cin >> tmp; // 读取依赖关系
char t1 = tmp[0] - 64, t2 = tmp[tmp.size()-1] - 64; // 转换为顶点编号
if(graph[t1][t2] == 0) degree[t2]++; // 更新入度
graph[t1][t2] = 1; // 添加依赖关系
int p = top(); // 进行拓扑排序
if(flag == 0){ // 如果还没有找到答案或矛盾
if(p == 1){
printf("Sorted sequence determined after %d relations: ",i);
cout << ans << ".\n"; //直接输出排序结果(我是傻逼,我就不放在printf)
flag = 1;
}else if(p == -1){
printf("Inconsistency found after %d relations.\n",i); //有环
flag = 1;
}
}
}
if(!flag) printf("Sorted sequence cannot be determined.\n");//全else时就是无法排序
}
是100分但是RE了一个点。。。
