[数据结构与算法]A. Book 拓扑排序(cf) + dp

原题链接：Problem - A - Codeforces

题目大意：给你一本书，有n页，每一次读这本书的时候都是从第一页读到第n页。每页有一个对应的list，每页对应有k页，必须读懂这k页才能读懂这一页（是不是很像拓扑排序）。

思路：所以用bfs进行拓扑排序，并且用dp来维护状态：要读懂的这一页是在这一页前面还是后面，当前这一遍就可以读完还是下次才能读完......

ans为-1的情况就是最后还有点前面还有点没读懂。有环的情况不会在队列中死循环，因为num[i]不为0时i是进不了队列的。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))

const int N = 2e5 + 10;
vector<int> e[N];
int num[N];
ll dp[N];

int main()
{
    int n, k, t;
    scanf("%d", &t);
    queue<int> q;
    while(t--){
    scanf("%d", &n);
    rep(i, n) e[i].clear(), dp[i] = 0;
    rep(i, n)
    {
        scanf("%d", &k);
        num[i] = k;
        rep(j, k)
        {
            int u;
            scanf("%d", &u);
            e[u].push_back(i);
        }
        if(!num[i]) q.push(i), dp[i] = 1;
    }
    ll ans = 1;
    while(q.size())
    {
        auto temp = q.front();
        q.pop();
        for(auto i : e[temp])
        {
            num[i]--;
            dp[i] = max(dp[i], dp[temp] + (i < temp));
            ans = max(ans, dp[i]);
            if(!num[i]) q.push(i);
        }
    }
    rep(i, n) if(num[i]){ ans = -1; break;} //如果还有没有解决的，说明有环，不可能成功
    printf("%lld\n", ans);
    }
    return 0;
}

?好久没做图了，复习复习！多思考，继续加油！