Codeforces 1463 E. Plan of Lectures（缩点，拓扑排序）

本文主要是介绍Codeforces 1463 E. Plan of Lectures（缩点，拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
要求你构造一个 $n$ 的排列，要满足：

$a [i]$ 出现在 $i$ 之前，如果 $a [i] = 0$ 代表这个数没有限制。仅对条件一保证一定有解。
有 $k$ 个特殊对 $(i, j)$ ，要求满足 $i$ 在排列中一定在 $j$ 的左边。

询问是否存在这样的排列。

思路：
这场的 $E$ 题简单的贪心和模拟就可以解决XD。

假设没有特殊对，那么直接按照条件1的限制跑一次拓扑排序（条件一实际构成了一个DAG图）。
有特殊对后，因为特殊对是要排列在一起的，所以不妨直接并查集缩点。将这些特殊对当做一个点再建图跑拓扑排序。然后对于每个点再按照之前在特殊对中的次序展开。
那么咋判断无解的情况呢？因为原本就是一个DAG图，所以新的图中也不应该出现环（出现了就无解）。那么无解就是特殊对构成的次序有环，或者特殊对的次序不满足条件一的限制。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;const int maxn = 3e5 + 7;
int nex[maxn],fa[maxn],deg[maxn];
int cnt,pos[maxn];
vector<int>G[maxn],a,ans;
int findset(int x) {if(fa[x] == x) {return x;}return fa[x] = findset(fa[x]);
}
void Union(int x,int y) {int rx = findset(x),ry = findset(y);if(rx != ry) {fa[ry] = rx;}
}
void bfs(int x) {queue<int>q;q.push(x);ans.push_back(x);while(!q.empty()) {int now = q.front();q.pop();for(int i = 0;i < G[now].size();i++) {int v = G[now][i];deg[v]--;if(deg[v] == 0) {q.push(v);ans.push_back(v);}}}
}int main() {int n,k;scanf("%d%d",&n,&k);int root = 0;for(int i = 1;i <= n;i++) {int x;scanf("%d",&x);fa[i] = i;if(x == 0) root = i;a.push_back(x);}for(int i = 1;i <= k;i++) {int x,y;scanf("%d%d",&x,&y);nex[x] = y;Union(x,y);}for(int i = 1;i <= n;i++) {int x = findset(a[i - 1]),y = findset(i);if(x == y) continue;G[x].push_back(y);deg[y]++;}for(int i = 1;i <= n;i++) {if(i == findset(i)) {cnt++;}}root = findset(root);bfs(root);vector<int>res;for(int i = 0;i < ans.size();i++) {int now = ans[i];for(int j = now;j;j = nex[j]) {res.push_back(j);if(res.size() > n) {printf("0\n");return 0;}}}for(int i = 0;i < res.size();i++) {pos[res[i]] = i;}for(int i = 1;i <= n;i++) {int x = a[i - 1],y = i;if(pos[x] > pos[y]) {printf("0\n");return 0;}}for(int i = 0;i < res.size();i++) {printf("%d ",res[i]);}return 0;
}