#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 27;
int n,m,g[N][N],f[N][N];
void floyd(){
memcpy(f,g,sizeof g);
for(int k = 0;k < n;k++)
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
f[i][j] |= f[i][k] & f[k][j];
}
int check(){
for(int i = 0;i < n;i++)
if(f[i][i]) return 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < i;j++){
if(!f[i][j] && !f[j][i]) return 1;
}
}
return 2;
}
string getorder(){
char s[26];
for(int i = 0;i < n;i++){
int cnt = 0;
for(int j = 0;j < n;j++) cnt += f[i][j];
s[n - cnt - 1] = i + 'A';
}
return string(s,s + n);
}
int main(){
while(cin>>n>>m,n || m){
string str;
int type = 1;
memset(g,0,sizeof g);
for(int i = 1;i <= m;i++){
cin>>str;
if(type != 1) continue;
int a = str[0] - 'A',b = str[2] - 'A';
g[a][b] = 1;
floyd();
type = check();
if(!type) printf("Inconsistency found after %d relations.\n",i);
else if(type == 2){
string ans = getorder();
printf("Sorted sequence determined after %d relations: %s.\n",i,ans.c_str());
}
}
if(type == 1) printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
分析:
本题考察Floyd算法在传递闭包问题上的应用。给定若干对元素和若干对二元关系,并且关系具有传递性,通过传递性推导出尽量多的元素之间的关系的问题被称为传递闭包。比如a < b,b < c,就可以推导出a < c,如果用图形表示出这种大小关系,就是a到b有一条有向边,b到c有一条有向边,可以推出a可以到达c,找出图中各点能够到达点的集合,就类似于Floyd算法求图中任意两点间的最短距离。Floyd求解传递闭包问题的代码如下:
void floyd(){
for(int k = 0;k < n;k++)
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
f[i][j] |= f[i][k] & f[k][j];
}
只是对原来算法在状态转移方程上略加修改 就能够求解传递闭包问题了。f[i][j] = 1表示i可以到达j ( i < j),f[i][j] = 0表示i不可到达j。只要i能够到达k并且k能够到达j,那么i就能够到达j,这就是上面代码的含义。
对于本题而言,给定n个元素和一堆二元关系,依次读取每个二元关系,在读取第i个二元关系后,如果可以确定n个元素两两间的大小关系了,就输出在几对二元关系后可以确定次序,并且次序是什么;如果出现了矛盾,就是A < B并且B < A这种情况发生了就输出多少对二元关系后开始出现矛盾;如果遍历完所有的二元关系还不能确定所有元素间的大小关系,就输出无法确定。
可以发现,题目描述要求按顺序遍历二元关系,一旦前i个二元关系可以确定次序了就不再遍历了,即使第i + 1对二元关系就会出现矛盾也不去管它了。对于二元关系的处理和之前的做法一样,A < B,就将f[0][1]设为1,题目字母只会在A到Z间,因此可以映射为0到25这26个元素,如果f[0][1] = f[1][0] = 1,就可以推出f[0][0] = 1,此时A < B并且A > B发生矛盾,因此在f[i][i]= 1时发生矛盾。
下面详细分析下求解的步骤:首先每读取一对二元关系,就执行一遍Floyd算法求传递闭包,然后执行check函数判断下此时是否可以终止遍历,如果发生矛盾或者次序全部被确定就终止遍历,否则继续遍历。在确定所有的次序后,需要输出偏序关系,因此需要执行下getorder函数。注意这里的终止遍历仅仅是不再针对新增的二元关系去求传递闭包,循环还是要继续的,需要读完数据才能继续读下一组数据。
下面设计check函数和getorder函数。
int check(){
for(int i = 0;i < n;i++)
if(f[i][i]) return 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < i;j++){
if(!f[i][j] && !f[j][i]) return 1;
}
}
return 2;
}
如果f[i][i] = 1就发生矛盾了,可以返回了;如果f[i][j] = f[j][i] = 0表示i与j之间的偏序关系还没有确定下来,就需要继续读取下一对二元关系;如果所有的关系都确定了,就返回2。
string getorder(){
char s[26];
for(int i = 0;i < n;i++){
int cnt = 0;
for(int j = 0;j < n;j++) cnt += f[i][j];
s[n - cnt - 1] = i + 'A';
}
return string(s,s + n);
}
确定所有元素次序后如何判断元素i在第几个位置呢?f[i][j] = 1表示i < j,因此计算下下i小于元素的个数cnt,就可以判定i是第cnt + 1大的元素了。
```