佛山网站建设的市场,手工制作大全视频,湖北建设人力资源网站,青岛网站建设公司好找吗文章目录 一、题目排序题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示 二、题解基本思路#xff1a;代码 一、题目
排序
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的… 文章目录 一、题目排序题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示 二、题解基本思路代码 一、题目
排序
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列例如一个有序的数列 A , B , C , D A,B,C,D A,B,C,D 表示 A B , B C , C D AB,BC,CD AB,BC,CD。在这道题中我们将给你一系列形如 A B AB AB 的关系并要求你判断是否能够根据这些关系确定这个数列的顺序。
输入格式
第一行有两个正整数 n , m n,m n,m n n n 表示需要排序的元素数量 2 ≤ n ≤ 26 2\leq n\leq 26 2≤n≤26第 1 1 1 到 n n n 个元素将用大写的 A , B , C , D , … A,B,C,D,\dots A,B,C,D,… 表示。 m m m 表示将给出的形如 A B AB AB 的关系的数量。
接下来有 m m m 行每行有 3 3 3 个字符分别为一个大写字母一个 符号一个大写字母表示两个元素之间的关系。
输出格式
若根据前 x x x 个关系即可确定这 n n n 个元素的顺序 yyy..y如 ABC输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前 x x x 个关系即发现存在矛盾如 A B , B C , C A AB,BC,CA AB,BC,CA输出
Inconsistency found after x relations.
若根据这 m m m 个关系无法确定这 n n n 个元素的顺序输出
Sorted sequence cannot be determined.
提示确定 n n n 个元素的顺序后即可结束程序可以不用考虑确定顺序之后出现矛盾的情况
样例 #1
样例输入 #1
4 6
AB
AC
BC
CD
BD
AB样例输出 #1
Sorted sequence determined after 4 relations: ABCD.样例 #2
样例输入 #2
3 2
AB
BA样例输出 #2
Inconsistency found after 2 relations.样例 #3
样例输入 #3
26 1
AZ样例输出 #3
Sorted sequence cannot be determined.提示 2 ≤ n ≤ 26 , 1 ≤ m ≤ 600 2 \leq n \leq 26,1 \leq m \leq 600 2≤n≤26,1≤m≤600。
二、题解
基本思路
很明显这是一道拓扑排序的题基本是是个模板题考察的是对拓扑排序得理解。输出结果有三种再每次输入一对关系后进行拓扑排序判断一拓扑序列结果为n个元素且最长链也得是n二图中不能有环有环即存在矛盾。而拓扑排序可以判断一个图中有没有环当拓扑序列的长度不是已读入元素的个数时说明有环。三在输入m个关系后前俩个都不是说明还没确定关系
代码
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
#define fi first
#define se second
#define repn(i,o,n) for(int io;in;i)
#define rep(i,o,n) for(int io;in;i)
const int N 30;
int n,m,d[N],rd[N];
vectorint edge[N];
setchar b;//存放当前读入的元素用count函数来判断有没有读入
bool flagfalse;//还没找到答案
//1.拓扑序列结果为n个元素且最长链也得是n
//2.图中不能有环有环即存在矛盾
//3.在输入m个关系后拓扑序列的结果!n inline void TopoSort(int num){queuepairint,int q;//第一个参数存得是点第二个是以该节点为结尾得链得长度 vectorint ans;//存放拓扑序列 int maxn0;//找最长链 repn(i,1,n)//入度为0的点且已经读入了该点的点入队 if(!rd[i]b.count((char)(iA-1))) q.push({i,1});while(!q.empty()){auto xq.front();q.pop();ans.push_back(x.fi);//拓扑序列每个节点出队一次 for(auto y:edge[x.fi])if(--rd[y]0){q.push({y,x.se1});maxnmax(maxn,x.se1); //找到最长链 }}if(maxnn){//最长链为n个元素说明已经确定了n个元素的顺序 coutSorted sequence determined after num ;coutrelations: ;rep(i,0,ans.size()){cout(char)(ans[i]A-1);//输出拓扑序列 }cout.endl;//注意还得输出个. flagtrue; return ;}//coutans.size()endl;if(ans.size()!b.size()){coutInconsistency found after ; coutnum relations.endl;flagtrue;return ;}
}void solve() {cinnm;repn(i,1,m) {string s;cins;b.insert(s[0]),b.insert(s[2]);edge[s[0]-A1].push_back(s[2]-A1);d[s[2]-A1];repn(i,1,n)rd[i]d[i];TopoSort(i);if(flag) return ;if(im){//im时前两个都不是说明还没确定关系 coutSorted sequence cannot be determined.endl;}}}signed main() {//IOS;int T1;//cinT;while(T--) {solve();}return 0;
}
