A. Book

拓扑序我们一眼就能看出来
主要是如何求读书的遍数
我最开始想的就是 把拓扑序处理出来 类似于要几遍上升序列能把他全部覆盖
显然求一遍不上升子序列即可
但是 我们观察这个例子

显然 我们只需要一遍的
因为我们看书 是在线的 看完了这个我们直接就必须加进去了
所以我们考虑每次看书 要是deg0 我们就直接加进一个优先队列
首先优先队列里面放的{当前第几趟，页数大小}
显然我们如果deg0时 v>u我们就可以付当前趟数else我们就不得不加1了
然后我们再贪心的从当前趟数小的出发 再选择页数小的开始删边 就可以了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int deg[N],n;
vector<int>g[N];
int ans;
bool check() {
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
    for(int i=1;i<=n;i++)if(!deg[i])q.push({1,i});
    while(q.size()){
        auto [s,u]=q.top();q.pop();
        ans=max(ans,s);
        for(auto v:g[u]){
            deg[v]--;
            if(!deg[v]){
                if(v>u)q.push({s,v});
                else q.push({s+1,v});
            }
        }
    }
    for(int i=1;i<=n;i++)if(deg[i]>0)return 1; //有环的是根本不可能度为0
    return 0;
}
void solve() {
    cin>>n;
    ans=0;
    for(int i=0;i<=n;i++)deg[i]=0,g[i].clear();
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        while(x--){
            int y;cin>>y;
            g[y].push_back(i);
            deg[i]++;
        }
    }
    if(check())cout<<-1<<endl;
    else cout<<ans<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

原文地址：http://www.cnblogs.com/ycllz/p/16826231.html