洛谷——P1347 排序（图论-拓扑排序）

---

一、题目

排序

题目描述

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

输入格式

第一行有两个正整数 $n,m$，$n$ 表示需要排序的元素数量，$2\le n\le 26$，第 $1$ 到 $n$ 个元素将用大写的 $A,B,C,D,\dots$ 表示。$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 x 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

样例输出 #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.

提示

$2\le n\le 26,1\le m\le 600$。

二、题解

基本思路：

• 很明显这是一道拓扑排序的题，基本是是个模板题，考察的是对拓扑排序得理解。
• 输出结果有三种，再每次输入一对关系后进行拓扑排序判断
• 一：拓扑序列结果为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;
}