算法1 Floyd
$O(m*n^3)$
C++ 代码
/*
floyd求传递闭包
i->j j->k --> i->k i能到j,j能到k,推出i能到k
一开始
g[i][j]=1(true),说明i->j,i能到j
g[i][j]=0(false),说明i到不了j
floyd算法:
初始化dist[i][j]=g[i][j]
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
如果(dist[i][j]==1(true) && dist[j][k]==1(true)) i能到j,j能到k
那么dist[i][k]=1(true) i能到k
本题:
floyd求完传递闭包后
i<j,则dist[i][j]=1,i和j无关,则dist[i][j]=0
判断三种状态:
1.矛盾,dist[i][i]=1,i>i,显然不对,i到不了自己
2.状态正好确定,对于每个i!=j,dist[i][j]或者dist[j][i]必有一个1()
3.没有确定解,存在i!=j,dist[i][j]=0且dist[j][i]=0,i与j无关
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int g[N][N],dist[N][N];
int st[N];
int n,m;
void floyd()
{
memcpy(dist,g,sizeof dist);
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dist[i][j] |= dist[i][k] && dist[k][j];
//(i->k,k->j)--->(i->j)
}
int check()
{
//1.检查是否存在矛盾
for(int i=0;i<n;i++)
if(dist[i][i])
return 2;
//2.检查是否是无确定解,即是否存在(i,j) i,j关系没确定且j,i关系也没确定
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
if(!dist[i][j] && !dist[j][i])
return 0;
//3.有确定解
return 1;
}
//找到当前还没输出的中最小的
char get_min()
{
for(int i=0;i<n;i++)
{
if(!st[i])
{
bool flag=true;//表明当前还没输出的中还没有比它小的
for(int j=0;j<n;j++)
{
if(st[j] || j==i) continue;//输出过了,或者j=i,跳过
else if(dist[j][i]==1)//存在没输出过且,j比i小,i就不是当前最小
flag=false;
}
if(flag==true)
{
st[i]=true;
return 'A'+i;
}
}
}
}
int main()
{
while(cin>>n>>m,n||m)
{
memset(g,0,sizeof g);
int type=0,t;
//type=0代表属于情况3,没有确定解,type=2代表矛盾,type=1代表情况2正好确定状态
//t用来记录迭代次数
for(int i=1;i<=m;i++)
{
char str[5];
cin>>str;
int a=str[0]-'A',b=str[2]-'A';//跳过一个'>'号
if(!type)//如果还没确定状态的话
{
g[a][b]=1;//添加a<b的关系
floyd();
type=check();
if(type!=0) t=i;//记录此时迭代次数,结束循环
//虽然结束循环,但是还是要把数据输入完,否则影响下一轮数据
}
}
//1.无确定解
if(type==0) printf("%s\n","Sorted sequence cannot be determined.");
else if(type==2)
printf("Inconsistency found after %d relations.\n",t);
else
{
memset(st, 0, sizeof st);//标记每个数是否被输出
printf("Sorted sequence determined after %d relations: ", t);
for(int i=0;i<n;i++) printf("%c",get_min());
//每次输出一个当前没确定的最小的
printf(".\n");
}
}
return 0;
}
算法2 改进
$O(m*n^2)$
C++ 代码
/*
改进:
不需要floyd
新加一条边a<b
for(x=0;x<n;x++)
看看哪些x<a(dist[x][a])
直接dist[x][b]=1
看看哪些b<x(dist[b][x])
直接dist[a][x]=1
for(y=0;y<n;y++)
看看哪些x<a 且 b<y
dist[x][y]=1
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int d[N][N];
int st[N];
int n,m;
int check()
{
//1.检查是否存在矛盾
for(int i=0;i<n;i++)
if(d[i][i])
return 2;
//2.检查是否是无确定解,即是否存在(i,j) i,j关系没确定且j,i关系也没确定
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
if(!d[i][j] && !d[j][i])
return 0;
//3.有确定解
return 1;
}
//找到当前还没输出的中最小的
char get_min()
{
for(int i=0;i<n;i++)
{
if(!st[i])
{
bool flag=true;//表明当前还没输出的中还没有比它小的
for(int j=0;j<n;j++)
{
if(st[j] || j==i) continue;//输出过了,或者j=i,跳过
else if(d[j][i]==1)//存在没输出过且,j比i小,i就不是当前最小
flag=false;
}
if(flag==true)
{
st[i]=true;
return 'A'+i;
}
}
}
}
int main()
{
while(cin>>n>>m,n||m)
{
memset(d,0,sizeof d);
int type=0,t;
//type=0代表属于情况3,没有确定解,type=2代表矛盾,type=1代表情况2正好确定状态
//t用来记录迭代次数
for(int i=1;i<=m;i++)
{
char str[5];
cin>>str;
int a=str[0]-'A',b=str[2]-'A';//跳过一个'>'号
if(!type)//如果还没确定状态的话
{
d[a][b]=1;//添加a<b的关系
for(int x=0;x<n;x++)
{
if(d[x][a]) d[x][b]=1;
for(int y=0;y<n;y++)
{
if(d[b][y]) d[a][y]=1;
if(d[x][a] && d[b][y]) d[a][b]=1;
}
}
type=check();
if(type!=0) t=i;//记录此时迭代次数,结束循环
//虽然结束循环,但是还是要把数据输入完,否则影响下一轮数据
}
}
//1.无确定解
if(type==0) printf("%s\n","Sorted sequence cannot be determined.");
else if(type==2)
printf("Inconsistency found after %d relations.\n",t);
else
{
memset(st, 0, sizeof st);//标记每个数是否被输出
printf("Sorted sequence determined after %d relations: ", t);
for(int i=0;i<n;i++) printf("%c",get_min());
//每次输出一个当前没确定的最小的
printf(".\n");
}
}
return 0;
}