题目链接
题目大意
给你一本书 有n个章节
每个章节 有k个先导章节
你必须要先阅读了先导章节 才能阅读懂当前章节
你每次阅读只能从第一个章节开始以此类推 遇到不懂章节跳过
问你读几次可以全读懂 或者无论几次都不可以
题目思路
首先很轻易想到拓扑
对于每个章节的先导章节
连接一个先导章节到当前章节的边
然后将当前章节入度+1
然后建立一个优先队列
首先将入度为0的点填进去优先队列 章节id大小排序
然后该点的出点全部入度--
更新入度 若为0 继续填进优先队列
但是要注意一个问题就是 这个章节阅读顺序必须要从小到大开始
而每次重新开始会使答案++
问题是如何让优先队列知道重新开始了
我另外写了一个队列 将所有 即将放入优先队列里的先放入普通队列里
然后优先队列是空时 将普通队列和优先队列互换 ans++
这样还会有一个问题 就是有的时候 你要填入普通队列的节点的章节id大于当前章节
这种情况该章节可以在当前ans次看书时学到 就填入优先队列
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int t,n,k;
int vis[maxn];
vector<int >v[maxn];
int ru[maxn];struct node{int id;bool operator < (const node & x)const{return x.id<id;}
};
priority_queue<node >q;
queue<node >qq;
void init()
{while(!qq.empty())qq.pop();while(!q.empty())q.pop();for(int i=0;i<=n;i++){v[i].clear();ru[i]=0;vis[i]=0;}
}
int main()
{cin>>t;while(t--){scanf("%d",&n);init();for(int i=1;i<=n;i++){scanf("%d",&k);for(int j=1;j<=k;j++){int x;scanf("%d",&x);v[x].push_back(i);ru[i]++;}}int num=0;for(int i=1;i<=n;i++){if(ru[i]==0){q.push(node{i});//num++;}}int ans=1;while(1){//cout<<num<<" num"<<endl;if(q.empty())//若两个队列都是空 就说明没有章节可以学了 退出{if(qq.empty()){break;}else {while(!qq.empty()){//cout<<22<<endl;node tmp=qq.front();qq.pop();q.push(tmp);}}ans++;}//cout<<"ans "<<ans<<"num "<<num<<endl;node now=q.top();q.pop();int x=now.id;if(vis[x])continue;num++;if(num==n){break;//num=n 代表着所有章节学习完毕}vis[x]=1;for(int i=0;i<v[x].size();i++){int y=v[x][i];ru[y]--;if(ru[y]==0&&vis[y]==0){if(y<x)qq.push(node{y});else q.push(node{y});}}}//cout<<num<<"num"<<endl;if(num==n)cout<<ans<<endl;else cout<<-1<<endl;}return 0;
}