题意

题目链接

需要寻找一种可行的候选人列表并输出，注意每个人在候选人列表找出第一个自己的祖先就会送出礼物。

解析

首先，如果一个人是某一个人的送礼物目标，则这个人就一定会出现在答案序列里。

而如果一个人的祖先已经出现在名单里了的话，则这个祖先的所有儿子即使后续再在列表中出现，也是无意义的。因此我们考虑拓扑排序，建一张反图，并得出该图的拓扑序，再除去其中不成为任何人的礼物目标的无意义序号。

这样我们得到了一张图，根据上述性质，如果当前根据拓扑拟定的方案无法满足每个人的要求，则一定不存在一种方案能够满足，因为该方案已经让需要较早出现的点尽可能早出现了。因此，我们只需要判断该方案能否满足要求，若不能，输出 $-1$。

我们用拓扑序（已去掉不需要的点），即目前的方案遍历每一个点，每一次将该点以及该点跑正图能够到达的点，也就是该点的所有儿子的实际送礼物目标都标记为这个点。当然，已经标记过的点不会被覆盖。

最后再将得到的这个目标与每个人的原始要求一一对比，若出现不符合的，输出 $-1$ , 否则输出该方案即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
struct edge{
    int to,next,from,pre;
}e[N<<1];
int head[N],cnt,prehead[N];
inline void add(int x,int y){//反图为 next，正图为 pre。 
    e[++cnt].to=y;
    e[cnt].next=head[x];
    e[cnt].from=x;
    e[cnt].pre=prehead[y];
    head[x]=cnt;
    prehead[y]=cnt;
}
int a[N],ru[N];
bool inans[N];
int tp[N],tot,Cnt;//tp[]表示拓扑序 
int ans[N];
inline void topo(){//找拓扑序 
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!ru[i]) q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        tp[++tot]=u;
        q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            ru[v]--;
            if(!ru[v]) q.push(v);
        }
    }
}
int fa[N];//表示每个点实际的送礼物目标 
void dfs(int u, int f) {
    if (fa[u]) {
        return;
    }
    fa[u] =f;
    for (int i=prehead[u];i;i=e[i].pre) {
        int v=e[i].from;
        dfs(v,f);
    }
}
 
int main() {
   scanf("%d%d",&n,&m);
    for (int i=1,x,y;i<=m;i++) {
        scanf("%d%d",&x,&y);
        add(y,x);
        ru[x]++;
    }
    for (int i=1;i<=n;i++) {//统计那些点需要出现在答案里 
        scanf("%d",&a[i]);
        inans[a[i]]=true;
    }
    topo();
    for (int i=1;i<=n;i++) {
        if (inans[tp[i]]) {//只有需要成为目标的点才需要遍历。 
            dfs(tp[i],tp[i]);
            ans[++Cnt]=tp[i];//记录答案方案 
        }
    }
    for (int i=1;i<=n;i++) {//将实际目标与需求目标对比 
        if (fa[i]!=a[i]) {
            cout<<-1;
            return 0;
        }
    }
    printf("%d\n",Cnt);
    for (int i=1;i<=Cnt;i++) 
        printf("%d\n",ans[i]);
    return 0;
}