CF1573C. Book(拓扑排序 最长路)

linkkkk

题意：

每个书有nnn页，每页都有前置页，学会这些前置页你才能够学会这页。每次阅读都是从111到nnn的顺序，问需要阅读几次才能够学完这本书。

思路：

对于每页和他的前置页，建图，u−>vu->vu−>v表示学会vvv必须要学会uuu，如果说u

求最长路+1+1+1就是答案。

代码：

#includeusingnamespacestd;constintmaxn=2e5+10,inf=0x3f3f3f3f;inth[maxn],e[maxn],ne[maxn],w[maxn],idx;intdin[maxn],dp[maxn],n;vectortop;voidadd(intu,intv,intww){e[idx]=v,ne[idx]=h[u],w[idx]=ww,h[u]=idx++;}booltopsort{top.clear;queueq;for(inti=1;i<=n;i++)if(!din[i])q.push(i);while(!q.empty){intt=q.front;q.pop;top.push_back(t);for(inti=h[t];~i;i=ne[i]){intj=e[i];if(!--din[j])q.push(j);}}returntop.size==n;}intmain{int_;cin>>_;while(_--){memset(h,-1,sizeofh);idx=0;memset(din,0,sizeofdin);cin>>n;for(inti=1;i<=n;i++){intm;cin>>m;for(intj=1;j<=m;j++){intx;cin>>x;if(x>i)add(x,i,1);elseadd(x,i,0);din[i]++;}}if(!topsort)puts("-1");else{intans=0;memset(dp,0,sizeofdp);for(intnow:top){for(inti=h[now];~i;i=ne[i]){intj=e[i];dp[j]=max(dp[j],dp[now]+w[i]);}}for(inti=1;i<=n;i++)ans=max(ans,dp[i]);cout<