P1347 排序

题意
依次给一些具有排序关系的序列，问你在能否在若干个序列之后确定元素的顺序、判断元素关系存在矛盾、判断无法确认元素顺序

思路
对于每一个排序关系均进行 toposort，后面就是 toposort 判环（出现矛盾），toposort 判顺序，无法确认唯一关系。
详见代码或看洛谷题解区

代码

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;
int n, m, now;
set<int> u;
vector<int> in, rin;
vector<vector<int>> e;

void toposort(int x){
	int ans = 0, sum = 0;
	queue<pii> q;
	string ss;
	for(auto a : u){
		if(in[a] == 0){
			q.push({a, 1});
			++ sum;
		}
	}
	while(q.size()){
		pii u = q.front(); q.pop();
		ans = max(ans, u.second);
		ss += (u.first + 'A');
		for(auto a : e[u.first]){
			-- in[a];
			if(in[a] == 0){
				q.push({a, u.second + 1});
				++ sum;
			}
		}
	}
	if(ans == n){
		cout << "Sorted sequence determined after " << x << " relations: " << ss << ".\n";
		exit(0);
	}
	if(sum != now){
		cout << "Inconsistency found after " << x << " relations.\n";
		exit(0);
	}
	return ;
}

void solve(){
	cin >> n >> m;
	rin = in = vector<int> (n + 1, 0);
	e = vector<vector<int>> (n + 1, vector<int>());
	vector<string> q;
	string ss;
	for(int i = 0; i < m; ++ i){
		cin >> ss;
		q.push_back(ss);
	}
	for(int i = 1; i <= m; ++ i){
		ss = q[i - 1];
		e[ss[0] - 'A'].push_back(ss[2] - 'A');
		u.insert(ss[0] - 'A');
		u.insert(ss[2] - 'A');
		now = u.size();
		++ rin[ss[2] - 'A'];
		in = rin;
		toposort(i);
	}
	cout << "Sorted sequence cannot be determined.\n";
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}