文章目录
- 一、题目
- 排序
-
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
-
- 样例输入 #1
- 样例输出 #1
- 样例 #2
-
- 样例输入 #2
- 样例输出 #2
- 样例 #3
-
- 样例输入 #3
- 样例输出 #3
- 提示
- 二、题解
-
- 基本思路:
- 代码
一、题目
排序
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列
输入格式
第一行有两个正整数
接下来有 <
符号,一个大写字母,表示两个元素之间的关系。
输出格式
若根据前 yyy..y
(如 ABC
),输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前
Inconsistency found after x relations.
若根据这
Sorted sequence cannot be determined.
(提示:确定
样例 #1
样例输入 #1
4 6
A<B
A<C
B<C
C<D
B<D
A<B
样例输出 #1
Sorted sequence determined after 4 relations: ABCD.
样例 #2
样例输入 #2
3 2
A<B
B<A
样例输出 #2
Inconsistency found after 2 relations.
样例 #3
样例输入 #3
26 1
A<Z
样例输出 #3
Sorted sequence cannot be determined.
提示
二、题解
基本思路:
- 很明显这是一道拓扑排序的题,基本是是个模板题,考察的是对拓扑排序得理解。
- 输出结果有三种,再每次输入一对关系后进行拓扑排序判断
- 一:拓扑序列结果为n个元素且最长链也得是n
- 二:图中不能有环,有环即存在矛盾。而拓扑排序可以判断一个图中有没有环,当拓扑序列的长度不是已读入元素的个数时,说明有环。
- 三:在输入m个关系后,前俩个都不是,说明还没确定关系
代码
#include<bits/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 i=o;i<=n;i++)
#define rep(i,o,n) for(int i=o;i<n;i++)
const int N = 30;
int n,m,d[N],rd[N];
vector<int> edge[N];
set<char> b;//存放当前读入的元素,用count函数来判断有没有读入
bool flag=false;//还没找到答案
//1.拓扑序列结果为n个元素且最长链也得是n
//2.图中不能有环,有环即存在矛盾
//3.在输入m个关系后,拓扑序列的结果!=n
inline void TopoSort(int num){
queue<pair<int,int>> q;//第一个参数存得是点,第二个是以该节点为结尾得链得长度
vector<int> ans;//存放拓扑序列
int maxn=0;//找最长链
repn(i,1,n)//入度为0的点且已经读入了该点的点入队
if(!rd[i]&&b.count((char)(i+'A'-1))) q.push({i,1});
while(!q.empty()){
auto x=q.front();
q.pop();
ans.push_back(x.fi);//拓扑序列每个节点出队一次
for(auto y:edge[x.fi])
if(--rd[y]==0){
q.push({y,x.se+1});
maxn=max(maxn,x.se+1); //找到最长链
}
}
if(maxn==n){//最长链为n个元素说明已经确定了n个元素的顺序
cout<<"Sorted sequence determined after "<<num<<" ";
cout<<"relations: ";
rep(i,0,ans.size()){
cout<<(char)(ans[i]+'A'-1);//输出拓扑序列
}
cout<<'.'<<endl;//!!!注意还得输出个'.'
flag=true;
return ;
}
//cout<<ans.size()<<endl;
if(ans.size()!=b.size()){
cout<<"Inconsistency found after ";
cout<<num<<" relations."<<endl;
flag=true;
return ;
}
}
void solve() {
cin>>n>>m;
repn(i,1,m) {
string s;
cin>>s;
b.insert(s[0]),b.insert(s[2]);
edge[s[0]-'A'+1].push_back(s[2]-'A'+1);
++d[s[2]-'A'+1];
repn(i,1,n)
rd[i]=d[i];
TopoSort(i);
if(flag) return ;
if(i==m){//i==m时,前两个都不是,说明还没确定关系
cout<<"Sorted sequence cannot be determined."<<endl;
}
}
}
signed main() {
//IOS;
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
版权声明:本文为博主作者:JIAN LAI原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/2301_77012063/article/details/135412541