目录
题意
条件1：给定一颗树，每个结点必须在父节点之后出现
条件2：给定k个特殊点对u, v，u的下一个结点必须是v
现在要求出满足上述两个条件结点序列（每个结点有且只出现1次）
思路
根据k个点对给出的结点间关系进行缩点，重新建图，拓扑排序即可
下面是3种无解的情况：
- 当k个点对给出的结点间关系形成了环，那么无解：例如3->4->5->3 由于每个结点只能出现1次，所以无解
- 当k个点对给出的结点间关系使得结点出现的顺序违反了第1个条件，无解：例如条件1 3->4->5，而条件2给出的关系为3->5->4，这种情况就无解，判断方法为：设rank[i]是结点i在缩的点中的rank，那么在结点3，4，5这三个点缩成的点中，按照条件1 应该rank[3]<rank[4]<rank[5]，但是根据条件2进行缩点后，rank[3]<rank[5]<rank[4]。换句话说：根据条件1的限制，一个结点和它的父结点如果在同一个缩的点中，那么该结点的rank应该大于父节点的rank，所以一旦出现小于，就是违反了条件1
- 缩点后建的图中存在环，无解：比如缩点后有2个点,1->2, 2->1，那么根据条件1，1中的某个点需要在2中的某个点之后出现，但是一旦1中的点开始出现，那么根据条件2就需要一个接着一个出现，而不能中途出现2中的结点，所以无解
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
//----------------------
int id, p[MAXN], nex[MAXN], L[MAXN], rnk[MAXN], ind[MAXN], rt[MAXN]; //L[i]是结点i在缩点过后的图中的结点编号 rnk[i]是结点i在缩点中rank，这个是为了判断是否有违反了条件1的链
bool vis[MAXN];
vector<int> e[MAXN];
int main(void)
{
int n, k;
scanf("%d%d", &n, &k);
for(int i=1; i<=n; i++){
scanf("%d", &p[i]);
}
for(int i=1; i<=k; i++){
int u, v;
scanf("%d%d", &u, &v);
nex[u]=v;
vis[v]=1;
}
//缩点
for(int i=1; i<=n; i++){
if(vis[i]) continue;
L[i]=++id;
int now=0, x=nex[i];
rnk[i]=0;
rt[id]=i; //这个是记录缩的点中的根节点
while(x!=0 && L[x]==0){ //L[x]==0这个条件是为了防止有环，如果有环，那就会一直循环下去，所以要加入L[x]==0这个条件
L[x]=id;
rnk[x]=++now;
x=nex[x];
}
}
//判断是否有环，以及是否违反了条件1的限制（比如3->4->5（3是4的前置topic，4是5的前置topic），但是缩的点中的链为3->5->4，那么就必然出现一个结点，它的父节点（前置topic）的rnk大于该节点本身的rnk，本例子中就是结点4的rnk大于结点5的rnk）
for(int i=1; i<=n; i++){
//有环的话，比如3->4->5->3，那么这三个点vis[]均为1，那么在缩点的时候就会全部continue，不会给对应的L[]赋编号
if(L[i]==0){
printf("0\n");
return 0;
}
if(L[i]==L[p[i]] && rnk[i]<rnk[p[i]]){
printf("0\n");
return 0;
}
}
//对缩点后的图进行建图
for(int i=1; i<=n; i++){
if(p[i]==0) continue;
if(L[i]!=L[p[i]]){
e[L[p[i]]].emplace_back(L[i]);
ind[L[i]]++;
}
}
//对缩点后的图进行拓扑排序，然后检查是否有环，没环就说明排序出的序列就是合法的，有环的话就无解了
queue<int> que;
for(int i=1; i<=id; i++){
if(ind[i]==0){
que.push(i);
}
}
vector<int> ans;
while(!que.empty()){
int u=que.front();
que.pop();
ans.emplace_back(u);
for(int v:e[u]){
ind[v]--;
if(ind[v]==0){
que.push(v);
}
}
}
if(ans.size()!=id){ //缩点后的图有环的话就无解
printf("0\n");
}else{
for(auto u:ans){
int now=rt[u];
while(now!=0){
printf("%d ", now);
now=nex[now];
}
}
}
return 0;
}