博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ-1094 Sorting it All Out
阅读量:6604 次
发布时间:2019-06-24

本文共 1731 字,大约阅读时间需要 5 分钟。

 

一个字母,则入度加一,并把小的当成大的字母的一个的出度,如果有一个入度为0就输出,并把其其所有出度点减一个入度,循环n次,若一次循环出两个字母,则排序失败,但不跳出,因为一旦遇到了一次循环根本无法输出,则输入结束后输出Inconsistency found after t relations.,t为这条指令的序号(每输入一个指令就判断),当然,若当次就能判断顺序,我们就把t和输出顺序存下来,到最后再输出。

注意:如果排序已经成功,则不用再管有没有回路的情况,若已存在回路的情况,则不再管排序能不能成功,所以,当已经存在回路或已经成功排序时就不用再做处理了。

#include
using namespace std;int n,m,sh=0,a[1001]={
0},t,c[10001]={
0},b[101][101]={
0},loc[1001]={
0},d[10001]={
0};int a1[10000001],b1[10000001];int main(){ string s; while(cin>>n>>m&&n!=0&&m!=0){//只要还在输入 for(int i=1;i<=m;i++) { cin>>s;、、输入指令 if(s[1]=='>'){//如果中间的是大于 b[(s[0]-'A'+1)][0]++; b[(s[0]-'A'+1)][b[(s[0]-'A'+1)][0]]=(s[2]-'A'+1); b[(s[0]-'A'+1)][b[(s[0]-'A'+1)][0]]=i; a[(s[2]-'A'+1)]++; d[(s[2]-'A'+1)]++; } else {//如果中间的是小于 b[(s[2]-'A'+1)][0]++; b[(s[2]-'A'+1)][b[s[2]-'A'+1][0]]=(s[0]-'A'+1); a[(s[0]-'A'+1)]++; d[(s[0]-'A'+1)]++; } if(sh==0&&z==0){//如果还没排出序而且还不存在回路,则进行模拟 bool panda=0; for(int l=1;l<=n;l++){//要用其他东西存起来,不然排序失败就完了 c[l]=a[l]; } int BS=0; for(int s=1;s<=n;s++){ int ans=0; for(int j=1;j<=n;j++){ if(a[j]==0){ c[j]--; BS++;//输出的字母的个数加1 ans++; if(ans==2){//有多个入度为0的则排序失败,但还有继续排序 panda=1; } loc[s]=j;//输出顺序 int k=b[j][0]; for(int t=1;t<=k;t++){ c[b[j][t]]--; } } if(ans==2){ panda=1; } } for(int l=1;l<=n;l++){ a[l]=c[l]; } if(ans==0&&BS!=n){//如果不存在入度为0的点且还没有输出完,则存在回路 sh=2; t=i; panda=1;break; } else if(ans>=2){ panda=1; } }if(panda==0){//排序成功 if(z==0) z=i;}}for(int ss=1;ss<=n;ss++){ a[ss]=c[ss]=d[ss];}}if(z!=0){//输出 cout<<"Sorted sequence determined after "<
<<" relations: ";for(int ll=n;ll>=1;ll--)cout<
<<"."<

转载于:https://www.cnblogs.com/c201904xyorz/p/9990797.html

你可能感兴趣的文章
$ORACLE_HOME/bin/oracle执行文件
查看>>
免密码登陆
查看>>
加密和解密 tar
查看>>
我的友情链接
查看>>
[李景山php]每天TP5-20161216|thinkphp5-helper.php-1
查看>>
VMware、Workstation 使用
查看>>
Windows Server 2012正式版RDS系列⑽
查看>>
The MySQL server has gone away
查看>>
freebsd上配置rsync服务
查看>>
Hibernate导出表代码
查看>>
用户输入和while循环
查看>>
keystone验证安装
查看>>
将datatable 保存为 Excel文件(高效率版本)
查看>>
C/C++五大内存分区(转)
查看>>
System V 共享内存区
查看>>
springmvc_1(hello world)
查看>>
0.随笔——读后感
查看>>
Linux基本安全措施、加强系统账号密码安全、系统引导和登录安全、用户切换、su、sudo、grub菜单...
查看>>
StringUtils类方法解析
查看>>
CentOS 6.5下PXE+Kickstart无人值守安装操作系统
查看>>