AcWing 343. 排序
原题链接
简单
作者:
追着你行走
,
2021-01-05 00:20:46
,
所有人可见
,
阅读 374
Floyd 算法处理传递闭包问题
代码实现:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
#define max(a,b) (a>=b?a:b)
#define min(a,b) (a>=b?b:a)
int dist[30][30],n,m;
int main(){
while(cin>>n>>m,n){
memset(dist,0,sizeof(dist));
//linked matrix
int unsure=0,error=0;
for(int kk=1;kk<=m;kk++) {
char a,b;
scanf(" %c<%c",&a,&b); //pre-blank to ignore enter
dist[a-'A'+1][b-'A'+1]=1;
unsure=0; //init
//floyd
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j]|=dist[i][k]&dist[k][j];
}
}
}
//check
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(dist[i][j]==1&&dist[j][i]==1){
printf("Inconsistency found after %d relations.\n",kk);
for(int k=kk+1;k<=m;k++) scanf(" %c<%c",&a,&b);
error=1; break;
}
if(dist[i][j]==0&&dist[j][i]==0){
unsure=1;
continue; //later check error
}
//正常
//record
}
if(error==1) break;
}
if(error) break;
if(unsure==0){ //sorted
priority_queue<pair<int,int> > q;
for(int i=1;i<=n;i++){
int ans=0;
for(int j=1;j<=n;j++){
ans+=dist[i][j];
}
q.push(make_pair(ans,i));
}
printf("Sorted sequence determined after %d relations: ",kk);
for(int k=kk+1;k<=m;k++) scanf(" %c<%c",&a,&b);
while(q.size()){
cout<<char(q.top().second+'A'-1);
q.pop();
} cout<<'.'<<endl;
break;
}
}
if(error==0&&unsure==1)
cout<<"Sorted sequence cannot be determined.\n";
}
return 0;
}