题目大意：有 1 ~ N 个大写字母，且从 A 开始依次 N 个。再给你 M 个小于的关系，比如 A < B ，让你判断三种可能：
1、在第 i 个关系罗列之后，是否可以满足使得这 N 个字母能递增关系。
2、在第 i 个罗列之后，是否会出现矛盾，例如 A > B，而在第 i 个状态出现后，B > A ，故矛盾。
3、如果 M 个条件罗列完后都没有出现矛盾，且还无法判断 N 个字母的排列顺序，则输出 Sorted sequence cannot be determined.
在前两种情况中，输出最先满足的 i ，也就是说，按 m 个状态的顺序，满足任意一个条件后，其他条件都不用再判断。
思路与分析：
对于 A < B，我们建一个 A --> B 的有向图。
按 M 个状态的顺序，每次得到 A < B ，标记 a[A][B] 为 true，表示 A 能到达 B ，然后全图跑一遍 floyd 传递闭包，判断在第 i 个状态时，是否满足前两种情况。
1、在三层循环传递闭包结束后，判断图中任意两点间是否存在 A > B 且 B < A 的这种矛盾关系，即判断全图两点是否会有 a[i][j] = true 且 a[j][i] = true ，有的话，则判断为第二种情况，标记或输出当前 i 。
2、还需要判断的是，如果 a[i][j]==0 且 a[j][i]==0 ，则说明此时 i 与 j 点之间没有任何小于或大于关系，故在当前状态时，还未能判断出 N 个字母的关系。
可以先用数组存 M 个状态，或者是边输入边判断。但一定要注意的是，如果 floyd 判断为 false （即上一段中的两种情况），则还需要再判断任意两点 i j ，是否为上文中的第一种情况（即 a[i][j]==a[j][i]==true），是的话，则说明为题目所描述的第二种情况。
边输入边判断：
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#define inf 0x3f3f3f3f
#define maxn 100
using namespace std;
int n,m,cnt,b,w,res;
int head[maxn],in[maxn];
bool a[maxn][maxn];
char c[maxn];
struct Edge
{
int to;
int next;
}edge[maxn*maxn*];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
return;
}
inline bool floyd(int C)
{
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(a[i][k]&&a[k][j]) a[i][j]=true;
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(i==j) continue;
if((a[i][j]&&a[j][i])){
b=C;
return false;
}
if(a[i][j]==&&a[j][i]==) return false;
}
}
return true;
}
void solve()
{
queue<int> q;
while(!q.empty()) q.pop();
for(int i=;i<=n;i++) {if(!in[i]) q.push(i);}
int tot=;
while(!q.empty())
{
int x=q.front();
q.pop();
c[tot++]=(char)(x+'A'-);
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
in[v]--;
if(!in[v]) q.push(v);
}
}
c[tot]='\0';
return;
}
void init()
{
b=cnt=w=res=;
memset(c,,sizeof(c));
for(int i=;i<=n;i++) {
head[i]=in[i]=;
for(int j=;j<=n;j++){
a[i][j]=false;
}
}
}
int main()
{
//freopen("test.in","r",stdin);
while(~scanf("%d%d",&n,&m)){
if(n==&&m==) break;
init();
char s[];
for(int i=;i<=m;i++){
scanf("%s",s);
if(w||b>=inf) continue;
int A=s[]-'A'+,B=s[]-'A'+;
a[A][B]=true;
add(A,B),in[B]++;
if(floyd(inf)){
w=;
if(!b) b=i;
continue;
}
else{//可以不需要再进行一遍判断，只需要 floyd 保存 b 之后，最后返回即可。因为可能会先被 a[i][j]==a[j][i]==0 先返回而 b 未被赋值为 inf
for(int k=;k<=n;k++){
for(int j=;j<=n;j++){
if(k==j) continue;
if(a[k][j]&&a[j][k]) {res=i;b=inf;}
}
}
}
}
if(w){
solve();
printf("Sorted sequence determined after %d relations: %s.\n", b,c);
}
else{
if(b){printf("Inconsistency found after %d relations.\n", res);}
else printf("Sorted sequence cannot be determined.\n");
}
}
}
存数组再遍历 M 个状态：
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#define inf 0x3f3f3f3f
#define maxn 30
using namespace std;
int n,m,cnt,b,w;
int head[maxn],in[maxn];
bool a[maxn][maxn];
char c[maxn],s[][];
struct Edge
{
int to;
int next;
}edge[maxn*maxn*];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
return;
}
inline bool floyd(int C)
{
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(a[i][k]&&a[k][j]) a[i][j]=true;
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(i==j) continue;
if((a[i][j]&&a[j][i])||(a[i][j]==&&a[j][i]==)) return false;
}
}
return true;
}
void solve()
{
queue<int> q;
while(!q.empty()) q.pop();
for(int i=;i<=n;i++) {if(!in[i]) q.push(i);}
int tot=;
while(!q.empty())
{
int x=q.front();
q.pop();
c[tot++]=(char)(x+'A'-);
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
in[v]--;
if(!in[v]) q.push(v);
}
}
c[tot]='\0';
return;
}
void init()
{
b=cnt=w=;
memset(c,,sizeof(c));
memset(s,,sizeof(s));
memset(a,,sizeof(a));
memset(head,,sizeof(head));
}
int main()
{
//freopen("test.in","r",stdin);
while(~scanf("%d%d",&n,&m)){
if(n==&&m==) break;
init();
for(int i=;i<=m;i++){
scanf("%s",s[i]);
}
for(int i=;i<=m;i++){
int A=s[i][]-'A'+,B=s[i][]-'A'+;
a[A][B]=true;
if(floyd()){
for(int j=;j<=i;j++){
A=s[j][]-'A'+,B=s[j][]-'A'+;
add(A,B),in[B]++;
}
solve();
printf("Sorted sequence determined after %d relations: %s.\n",i,c);
w=;
}
else{
for(int k=;k<=n;k++){
for(int j=;j<=n;j++){
if(k==j) continue;
if(a[k][j]&&a[j][k]){
printf("Inconsistency found after %d relations.\n", i);
w=;
break;
}
if(w) break;
}
}
}
if(w) break;
}
if(!w) printf("Sorted sequence cannot be determined.\n");
}
}