【洛谷_P1347】排序


排序

题目

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列A,B,C,D 表示A<B,B<C,C<D。在这道题中,我们将给你一系列形如A<B的关系,并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入格式

第一行有两个整数n,m,n表示需要排序的元素数量,2<=n<=26,第1到n个元素将用大写的A,B,C,D…表示。m表示将给出的形如A<B的关系的数量。

接下来有m行,每行有3个字符,分别为一个大写字母,一个<符号,一个大写字母,表示两个元素之间的关系。

输出格式

若根据前x个关系即可确定这n个元素的顺序yyy…y(如ABC),输出

Sorted sequence determined after xxx relations: yyy…y.

若根据前x个关系即发现存在矛盾(如A<B,B<C,C<A),输出

Inconsistency found after 2 relations.

若根据这m个关系无法确定这n个元素的顺序,输出

Sorted sequence cannot be determined.

(提示:确定n个元素的顺序后即可结束程序,可以不用考虑确定顺序之后出现矛盾的情况)

输入输出样例
输入#1

4 6
A<B
A<C
B<C
C<D
B<D
A<B

输出#1

Sorted sequence determined after 4 relations: ABCD.

输入#2

3 2
A<B
B<A

输出#2

Inconsistency found after 2 relations.

输入#3

26 1
A<Z

输出#3

Sorted sequence cannot be determined.

解题思路
第一种情况:

我们记录一条最长链的长度,如果

len==nlen==n

len==n就输出队列里的内容

第二种情况

如果输入时

x==yx==y

x==y或者

du[i]!=0du[i]!=0

du[i]!=0则说明它有环,则是第二种情况

第三种情况

如果前两种情况都不是,就是第三种情况

code(注:一边输入一边拓扑,以保证第二种情况)

#include<iostream>
#include<cstdio>
using namespace std;

int n,m,b[1000],v[1000],d[1000];
int head[1000],tot,f[1000],l,ans[1000];

struct abc{
int to,next;
}s[1000];

void add(int x,int y)
{
s[++tot]=(abc){y,head[x]};
head[x]=tot;
}

void tp()
{
int hd=0,tl=0;
l=0;
for(int i=1;i<=n;i++)
{
ans[i]=f[i]=v[i]=0;
d[i]=b[i];
if(d[i]==0)
{
tl++;
v[i]=1;
f[tl]=i;
ans[i]=1;
}
}
while(hd<tl)
{
hd++;
int x=f[hd];
for(int i=head[x];i;i=s[i].next)
{
int y=s[i].to;
if(v[y]) continue;
d[y]--;
ans[y]=max(ans[x]+1,ans[y]);
l=max(l,ans[y]);
if(d[y]==0)
{
v[y]=1;
f[++tl]=y;
}
}
}
}

int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
char a;
int x,y;
cin>>a;
x=a-64;
cin>>a>>a;
y=a-64;
if(x==y)
{
printf("Inconsistency found after %d relations.",i);
return 0;
}
add(x,y);
b[y]++;
tp();
for(int j=1;j<=n;j++)
if(d[j]>0)
{
printf("Inconsistency found after %d relations.",i);
return 0;
}
if(l==n)
{
printf("Sorted sequence determined after %d relations: ",i);
for(int j=1;j<=n;j++)
printf("%c",f[j]+64);
printf(".");
return 0;
}
}
printf("Sorted sequence cannot be determined.");
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【洛谷_P1347】排序

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【洛谷_P1347】排序
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏