http://acm.pku.edu.cn/JudgeOnline/problem?id=1094这个方法很简单，思路是这样的，对于每次输入一个关系后，我们就对输入进行一次拓扑排序，拓扑排序的结果有三种情况。
结果确定的两种情况：
第一种，如果排序后，序列中的节点数目<n,说明出现了环，因此应该直接输出，一旦结果确定，以后的输入就不用判断了。
第二种，如果排序后，节点数目刚好等于n，并且序列里相邻的节点已经明确出现了<,关系，说明大小关系已经确定了
还有一种，只能说明到目前为止知道的信息不足以判断，还需要继续看以后的输入才行
第三种情况，即排序后，节点数目刚好等于n，但是序列里相邻的节点还未明确出现<关系
代码如下：
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 26
#define debug
#undef debug
using namespace std;
bool top_sort(int G[MAX_N][MAX_N],int n ,int relation_no){
bool is_add[MAX_N];
int temp_g[MAX_N][MAX_N];
vector <int> sorted_res;
memset(is_add,false,sizeof(is_add));
for(int i = 0 ; i < MAX_N ; i++){
for(int j = 0 ; j < MAX_N ; j++)
temp_g[i][j] = G[i][j];
}
#ifdef debug
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++)
printf("%d ",temp_g[i][j]);
printf("\n");
}
#endif
while(true){
int next_add = -1;
for(int i = 0 ; i < n ; i++){
if(is_add[i]) continue;
bool can_be_add = true;
for(int j = 0 ; j < n ; j++){
can_be_add = can_be_add && (temp_g[j][i] == 0);
}
if(can_be_add){
is_add[i] = true;
next_add = i;
#ifdef debug
printf("%d ",i);
#endif
break;
}
}
if(next_add < 0) break;
sorted_res.push_back(next_add);
for(int j = 0 ; j < n ; j++){
temp_g[next_add][j] = 0;
}
}
if(sorted_res.size() < n){
printf("Inconsistency found after %d relations.\n",relation_no);
return true;
}
else{
bool is_determined = true;
for(int i = 1 ; i < sorted_res.size() ; i++){
is_determined = is_determined&&G[sorted_res[i-1]][sorted_res[i]];//attention please we should use G instead of temp_g
}
if(is_determined){
printf("Sorted sequence determined after %d relations: ",relation_no);
for(int i = 0 ; i < sorted_res.size() ; i++){
printf("%c",sorted_res[i]+'A');
}
printf(".\n");
return true;
}
else{
return false;
}
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m) && !(n==0 && m==0)){
char temp[MAX_N];
int g[MAX_N][MAX_N];
for(int i = 0 ; i < MAX_N ; i++){
for(int j = 0 ; j < MAX_N ; j++)
g[i][j] = 0;
}
bool is_determined = false;
for(int i = 0 ; i < m ; i++){
scanf("%s",temp);
g[temp[0]-'A'][temp[2]-'A'] = 1;
if(!is_determined){
is_determined = top_sort(g,n,i+1);
}
}
if(!is_determined)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
评论