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;
}