城市建设最好的网站,黄河勘测规划设计公司,成都网站建设的公司哪家好,php 网站开发架构题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列#xff0c;例如#xff0c;一个有序的数列 A,B,C,D表示 AB,BC,CD。在这道题中#xff0c;我们将给你一系列形如 AB的关系#xff0c;并要求你判断是否能够根据这些关系确定这个…题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列例如一个有序的数列 A,B,C,D表示 AB,BC,CD。在这道题中我们将给你一系列形如 AB的关系并要求你判断是否能够根据这些关系确定这个数列的顺序。
输入格式
第一行有两个正整数 n,m 表示需要排序的元素数量2≤n≤26第 1 到 n 个元素将用大写的 A,B,C,D,…A,B,C,D,… 表示。m 表示将给出的形如 AB 的关系的数量。
接下来有 m 行每行有 3 个字符分别为一个大写字母一个 符号一个大写字母表示两个元素之间的关系。
输出格式
若根据前 x 个关系即可确定这 n 个元素的顺序 yyy..y如 ABC输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前 x 个关系即发现存在矛盾如 AB,BC,CA输出
Inconsistency found after x relations.
若根据这 m 个关系无法确定这 n 个元素的顺序输出
Sorted sequence cannot be determined.
提示确定 n 个元素的顺序后即可结束程序可以不用考虑确定顺序之后出现矛盾的情况
输入输出样例
输入 #1复制
4 6
AB
AC
BC
CD
BD
AB输出 #1复制
Sorted sequence determined after 4 relations: ABCD.
输入 #2复制
3 2
AB
BA
输出 #2复制
Inconsistency found after 2 relations.
输入 #3复制
26 1
AZ
输出 #3复制
Sorted sequence cannot be determined.
说明/提示
2≤n≤26,1≤m≤600。
这道题考察的是拓扑排序AcWing 1191. 家谱树图论拓扑排序的模板-CSDN博客 模板在这
我们简单讲讲思路我们把输出分成三种形式题目描述先后对应1、2、3第1种是可以判断得出完整拓扑排序的情况第2种是有环的情况第3种就是这两个之外直接输出
第2种首先判断是否形成环了做法记录出现的字母个数如果最后得到的拓扑序列的大小 小于字母个数那么就是形成环了
第1种必须严格的得出所有字母之间的关系也就是说记录出现字母的个数必须等于拓扑序列的大小而且队列的大小要保持为1如果超过1了说明有不确定的关系
代码
#include bits/stdc.h
using namespace std;const int N 30;
int ind[N],oud[N],cpy[N];
vectorint e[N];
bool b[N];int n,m,cnt 0,type 0;void topsort(int idx){memcpy(ind,cpy,sizeof(cpy));queueint q;string ans ;bool ac true;for(int i1;in;i){if(!b[i]) continue;if(!ind[i]) q.push(i);}while(!q.empty()){if(q.size() 2) ac false;int u q.front();q.pop();ans char(u) 64;for(auto v : e[u]){ind[v] --;if(!ind[v]) q.push(v);}}// if(idx 28) cout ans ans.size() cnt endl;if(ans.size() cnt){// cout ans.size() cnt endl;type 2;printf(Inconsistency found after %d relations.\n,idx);}if(ans.size() n ac){type 1;printf(Sorted sequence determined after %d relations: ,idx);cout ans . endl;}
}int main()
{cin n m;string s;for(int i1;im;i){cin s;if(type) continue;int A s[0] - 64,B s[2] - 64;// cout A B endl;if(!b[A]){b[A] true;cnt ;}if(!b[B]){b[B] true;cnt ;}if(s[1] ){cpy[B] ,oud[A] ;e[A].push_back(B);}else{cpy[A] ,oud[B] ;e[B].push_back(A);}topsort(i);}if(!type) cout Sorted sequence cannot be determined. endl;return 0;
}
加油
