poj1094：http://poj.org/problem?id=1094
题解（一位大神的分析）
一、当输入的字母全部都在前n个大写字母范围内时：
（1）最终的图 可以排序： 在输入结束前如果能得到最终的图（就是用这n个字母作为顶点，一个都不能少）；而且最终得到的图 无环；
只有唯一一个 无前驱（即入度为0）的结点，但允许其子图有多个无前驱的结点。在这步输出排序后，不再对后续输入进行操作
（2）输出矛盾：在输入结束前如果最终图的子图有环， 在这步输出矛盾后，不再对后续输入进行操作
（3）输出无法确认排序：这种情况必须全部关系输入后才能确定，其中又有2种可能
①最终图的字母一个不缺，但是有多个 无前驱结点
②输入结束了，但最终的图仍然字母不全，与 无前驱结点 的多少无关
二、当输入的字母含有 非前n个大写字母 的字母时（超出界限）：
（1）输出矛盾：输入过程中检查输入的字母（结点），若 前n个大写字母 全部出现，则在最后一个大写字母出现的那一步 输出矛盾
（2）输出无法确认排序：最后一步输入后，前n个大写字母 仍然未全部出现，则输出 无法确认排序
PS：在使用“无前驱结点”算法时必须要注意，在“矛盾优 先”的规律下，必须考虑一种特殊情况，就是多个无前驱结点与环共存时的情况，即输入过程中子图都是有
多个无前驱结点，最后一步输入后出现了环，根据算法的特征，很容易输出“不能确认排序”，这是错的，必须适当修改算法，输出“矛盾”。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int counts[];
int temp[];
char relation[];
char seq[];
bool alpha[];
int n,m;
vector<vector<char> >v;
int topsort(int s){
int i,j,r,cnt;
bool flag;
r=,cnt=;
for( i=;i<n;i++)
temp[i]=counts[i];
flag=;
while(s--){
cnt=;
for( i=;i<n;i++){
if(temp[i]==){
j=i;cnt++;
}
}
if(cnt>=){
if(cnt>)flag=;
for( i=;i<v[j].size();i++)
temp[v[j][i]]--;
seq[r++]=j+'A';
temp[j]=-;seq[r]=;
}
else if(cnt==)return -;
}
if(flag){return r;}
else
return ;
}
int main(){
int i,j,t,k,c;
int determined;char ss[];
while(~scanf("%d%d",&n,&m)&&n&&m){
memset(counts,,sizeof(counts));
memset(alpha,false,sizeof(alpha));
v.clear();
v.resize(n);
c=;determined=;
for(i=;i<m;i++){
scanf("%s",relation);
counts[relation[]-'A']++;
v[relation[]-'A'].push_back(relation[]-'A');
if(!alpha[relation[]-'A']){
c++;alpha[relation[]-'A']=true;
}
if(!alpha[relation[]-'A']){
c++;alpha[relation[]-'A']=true;
}
if(determined==){
t=topsort(c);
if(t==-){
determined=-;k=i+;
}
else if(t==n){
determined=;k=i+;
strcpy(ss,seq);
}
}
} if(determined==-)
printf("Inconsistency found after %d relations.\n",k);
else if(determined==)
printf("Sorted sequence cannot be determined.\n");
else{
printf("Sorted sequence determined after %d relations: %s.\n",k,ss);
} }
}