主要思路

这道题的主要做法就是贪心了。我们枚举\(i\)从\(n-1\)到\(1\)，记\(vis[i]\)为编号为\(i\)的节点是否可以转移、\(arr[i]\)为\(i\)位置上的数，在转移关系集中寻找\((i,j), vis[j]=true\)的\(j\)。由于我们是从后向前转移，所以我们找到的这些\(j\)的位置都是在\(i\)之后的，符合转移要求。之后我们验证目前已转移的答案\(ans\)与满足条件的关系个数\(cnt\)与\(i\)的和是否为\(n\)，如果符合意味着转移符合条件，便直接进行转移；如果不符合，那么我们把该点的标记打上，意味着可以从此被转移。

代码

// CF1136D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 2000;
int arr[MAX_N], n, m, tmpx, tmpy, ans;
bool vis[MAX_N];
vector<int> cond[MAX_N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &tmpx, &tmpy), cond[tmpx].push_back(tmpy);
    vis[arr[n]] = true;
    for (int i = n - 1; i >= 1; i--)
    {
        int cnt = 0, siz = cond[arr[i]].size();
        for (int j = 0; j < siz; j++)
            if (vis[cond[arr[i]][j]])
                cnt++;
        if (cnt + ans + i == n)
            ans++;
        else
            vis[arr[i]] = true;
    }
    printf("%d", ans);
    return 0;
}