题意
给出n，代表有以A开始的n个字母，给出它们的m个小于关系（A<B）。 如果前i个关系可以确定n个字母的一个顺序就输出：
Sorted sequence determined after i relations: 排好的字母.
如果前i个关系开始导致矛盾，就输出：
Inconsistency found after i relations.
m个关系后还不能确定顺序就输出：
Sorted sequence cannot be determined.
代码
代码语言：javascript复制/*
g[i][j]为邻接矩阵，e[i]为i的入度
in==1代表有矛盾，d==1代表确定顺序
so存排好的顺序
*/
#include<cstdio>
#include<cstring>
#define N 30
int n, m, g[N][N], e[N], c[N], a, b, in, d, so[N];
char va, vb;
void topo()
{
memcpy(c, e, sizeof e);//复制e到c，因为后面要对c改动，所以不能直接用e
int i, top = -1;
for(i = 0; i < n; i )
if(!c[i])
{
c[i] = top;//模拟下标堆栈，把入度为0的点通过下标堆栈到c中
top = i;
}
for(i = 0; i < n; i )
{
if(top == -1)//n次循环中，若某次找不到入度为0的点，就会回到-1
{
in = 1;//说明存在环
return;
}
int u = top;//以top为起点
top = c[u];
so[i] = u;
for(int v = 0; v < n; v )
if(g[u][v] && (--c[v]) == 0)//去掉u出发的边后，入度为0的点
{
c[v] = top; //堆栈
top = v;
}
}
d = 1;
for(i = 1; i < n; i )//判断是否是确定的顺序
if(!g[so[i - 1]][so[i]])d = 0;//如果出现相邻两个没有给过偏序关系，那么就是不确定的顺序
}
int main()
{
//freopen("in.txt", "r", stdin);
while(~scanf("%d%d ", &n, &m) && n)
{
memset(g, 0, sizeof g);
memset(e, 0, sizeof e);
d = in = 0;
for(int i = 1; i <= m; i )
{
scanf("%c<%c ", &va, &vb);
a = va - 'A';
b = vb - 'A';
if(!g[a][b] && !d && !in)
{
g[a][b] = 1;
e[b] ;
topo();
if(in)
printf("Inconsistency found after %d relations.n", i);
else if(d)
{
printf("Sorted sequence determined after %d relations: ", i);
for(int j = 0; j < n; j )printf("%c", so[j] 'A');
printf(".n");
}
}
}
if(!d && !in)printf("Sorted sequence cannot be determined.n");
}
}
这个是我参考lrj的《入门经典》的板子写的，耗时0ms
代码语言：javascript复制#include <cstdio>
#include <cstring>
#define N 30
int n, m, g[N][N], c[N], t, ans;
char a, b, topo[N];
int dfs(int u)
{
c[u] = -1;
for(int v = 0; v < n; v )if(g[u][v])
{
if(c[v] < 0)return 0;
else if(!c[v] && !dfs(v))return 0;
}
c[u] = 1;
topo[--t] = u;
return 1;
}
int toposort()
{
t = n;
memset(c, 0, sizeof c);
for(int u = 0; u < n; u )
if(!c[u] && !dfs(u))return 0;
for(int i = 1; i < n; i )
if(!g[topo[i - 1]][topo[i]])return -1;
return 1;
}
int main()
{
// freopen("in.txt", "r", stdin);
while(~scanf("%d%d ", &n, &m) && n)
{
ans = -1;
memset(g, 0, sizeof g);
for(int i = 1; i <= m; i )
{
scanf("%c<%c ", &a, &b);
g[a - 'A'][b - 'A'] = 1;
if(ans == -1)
{
ans = toposort();
if(!ans)
printf("Inconsistency found after %d relations.n", i);
else if(ans == 1)
{
printf("Sorted sequence determined after %d relations: ", i);
for(int j = 0; j < n; j )printf("%c", topo[j] 'A');
printf(".n");
}
}
}
if(ans == -1)printf("Sorted sequence cannot be determined.n");
}
return 0;
}
