luogu P1347 排序
2024-09-02 21:49:32
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列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:
1:
4 6
A<B
A<C
B<C
C<D
B<D
A<B 2:
3 2
A<B
B<A 3:
26 1
A<Z
输出样例#1:
1:
Sorted sequence determined after 4 relations: ABCD.
2:
Inconsistency found after 2 relations.
3:
Sorted sequence cannot be determined.
topo排序
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int N = ;
queue<int>que;
int n,m;
bool vis[N];
struct node{
int v,next;
}edge[N*N/];
int many=;
int rd[N],rdd[N];int head[N];int num;
void Add_edge(int x,int y)
{
edge[++num].v=y;edge[num].next=head[x];head[x]=num;
}
int cnt;
int can[N];
int topsort()
{
cnt=;int num=;
for(int i=;i<=;i++)
{
rdd[i]=rd[i];
if(rdd[i]==&&vis[i])num++,que.push(i),can[++cnt]=i;
}
if(!num)return ;
bool a=;
while(!que.empty())
{
int u=que.front();
que.pop();int aa=;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].v;
rdd[v]--;
if(rdd[v]==)
{
can[++cnt]=v;
aa++;
if(aa>=)a=;
que.push(v);
}
}
}
if(cnt!=many)return ;
if(num>||a)return ;
return ;
}
int main()
{
scanf("%d%d",&n,&m);
char a[];
for(int i=;i<=m;i++)
{
scanf("%s",a);
int tmp=a[]-'A'+;
int ttmp=a[]-'A'+;
rd[ttmp]++;
if(!vis[tmp])many++;if(!vis[ttmp])many++;
vis[tmp]=; vis[ttmp]=;
Add_edge(tmp,ttmp);
if(topsort()==)
{
printf("Inconsistency found after %d relations.",i);return ;
}
if(!topsort()&&cnt==n)
{
printf("Sorted sequence determined after %d relations:",i);
for(int j=;j<=cnt;j++)
{
putchar(can[i]+'A'-);
}
//if(can)
printf(".");
return ;
}
}
puts("Sorted sequence cannot be determined.");
return ;
}
最新文章
- React使用antd Table生成层级多选组件
- 优化Web中的性能
- 精通Web Analytics 2.0 (3) 第一章:网站分析的新奇世界
- 【IOI2000】邮局设置问题
- typedef 用法及 指针函数 和 函数指针
- 配置oracle账号密码永不过期
- ASP.NET页面上传文件时提示文件大小超过请求解决方法
- 聊聊dmClock算法
- 从mysql主从复制到微信开源的phxsql
- Ruby on Rails Tutorial 第一章笔记
- ls 命令查看文件时候,按修改时间倒序或升序排列
- [wx]雪落香杉树人物关系图
- es6 class函数的用法,及兼容程度
- 在ASP.NET MVC中使用Knockout实践09,自定义绑定
- 有趣的js匿名函数写法(function嵌套)
- NOIP200606金明的预算方案
- [UIImage _isCached]: message sent to deallocated instance
- BZOJ5297 CQOI2018 社交网络 【矩阵树定理Matrix-Tree】
- Access如何判断字符串从左边第一个数字为5
- UICollectionView的cell创建直接从第三个数据开始问题
热门文章
- operator、explicit与implicit
- 牛客网暑期ACM多校训练营(第一场):D-Two Graphs
- linux误删除恢复
- 一个画ROC曲线的封装包
- PBFT性能会下降? 各种算法的对比。
- Python编码报错
- [muku][1 初始restful api] chorme安装jsonview 插件
- springmvc中RedirectAttributes、SessionFlashMapManager的作用
- 使用awk根据多维度统计系统tps
- Angular &; RxJS &; Typesc&#173;ript