题目：C. Book
题目链接：https://codeforces.com/contest/1573/problem/C
题意：有一本书，共n页（记为1 - n），每一次读书都是从第1页看到第n页，在理解第i页之前可能要先理解某些页数才能理解该页，问要理解所有的页数，最少需要读多少次书。
输入：第一行输入测试用例数t。
第二行输入书的页数n。
接下来n行：每行第一个数ki，表示在理解第i页前，需要先理解ki页书。接下来ki个数字，表示理解第i页前，需要理解的ki页书的具体页数。
输出：输出理解所有的页数所需要读的最少次数。如果不可能理解所有的页数，则输出-1。
样例输入：
1
4
1 2
0
2 1 4
1 2
输出：
2
样例解释：共1个测试用例。书的页数是4，理解第1页前需要先理解第2页，理解第2页前不需要理解其他页数。理解第3页前需要先理解第1页和第4页，理解第四页前需要先理解第2页。
第一遍读书看到第1页不能理解（因为第2页还没理解），看到第2页就能够理解第2页了。在看到第3页理解不了（因为第4页还没理解），看到第4页能够理解第4页（因为第2页已经理解）。
第二遍读书，第1页和第3页都能够理解了。
所以最少需要读两遍书。（第一遍理解2、4页，第二遍理解1、3页）
问题分析：拓扑排序。
解题思路：在理解i页前需要理解j页，那么我们就生成一条从j到i的有向边。用数组b来记录i点的入度，当一个点的入度为0时，说明它能够被理解了。用结构体存当前理解的页数x和当前已读的次数step，将结构体放进优先队列，在遍历一个点x的时候，遍历以x为起点的所有边，将边的终点的入度都 – 1，当点的入度为0时，入队。当队列为空时，判断是否有点的入度b[i]不为0，若有，则说明不存在拓扑排序，答案为-1。
错误：需要注意的是，若有边（1， 4），且4的入度为 1，那么队首到1时，理解4的读书次数和理解1的读书次数是一样的。但若有边（4， 1），且1的入度为 1，那么队首到1时，理解1的读书次数应该比理解4的读书次数多1。若用结构体应该按已读次数step从小到大排序，当已读次数一致时，应按x从小到大排序。故本题应用优先队列priority_queue存结构体。
错误代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> v[N];
int b[N];
struct st{
int x, step;
};
void solve(){
int n;
scanf("%d", &n);
for(int i = 0;i <= n + 1;i++){
v[i].clear();
b[i] = 0;
}
queue<st> q;
for(int i = 1;i <= n;i++){
int x, num;
scanf("%d", &x);
if(x == 0) q.push({i, 1});
else{
while(x--){
scanf("%d", &num);
b[i]++;
v[num].push_back(i);
}
}
}
for(int i = 1;i <= n;i++) sort(v[i].begin(), v[i].end());
int ans = -1;
while(!q.empty()){
int x = q.front().x, step = q.front().step;
q.pop();
ans = max(ans, step);
for(int i = 0;i < v[x].size();i++){
int t = v[x][i];
b[t]--;
if(b[t] == 0){
if(t > x) q.push({t, step});
else q.push({t, step + 1});
}
}
}
for(int i = 1;i <= n;i++){
if(b[i] != 0) ans = -1;
}
printf("%d\n", ans);
}
int main(void){
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
下面的测试用例错误代码输入的是1，正确答案应该是2。
1
7
0
1 1
1 1
1 3
1 2
3 4 5 7
1 2
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> v[N];
int b[N];
struct st{
int x, step;
bool operator < (const st &X) const{
if(step == X.step) return x > X.x;
return step > X.step;
}
};
void solve(){
int n;
scanf("%d", &n);
for(int i = 0;i <= n + 1;i++){
v[i].clear();
b[i] = 0;
}
priority_queue<st> pq;
for(int i = 1;i <= n;i++){
int x, num;
scanf("%d", &x);
if(x == 0) pq.push({i, 1});
else{
while(x--){
scanf("%d", &num);
b[i]++;
v[num].push_back(i);
}
}
}
for(int i = 1;i <= n;i++) sort(v[i].begin(), v[i].end());
int ans = -1;
while(!pq.empty()){
int x = pq.top().x, step = pq.top().step;
pq.pop();
ans = max(ans, step);
for(int i = 0;i < v[x].size();i++){
int t = v[x][i];
b[t]--;
if(b[t] == 0){
if(t > x) pq.push({t, step});
else pq.push({t, step + 1});
}
}
}
for(int i = 1;i <= n;i++){
if(b[i] != 0) ans = -1;
}
printf("%d\n", ans);
}
int main(void){
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
时间复杂度：O（nlong），因为每个点最多入队1次，出队1次。
空间复杂度：O(n)。
原文：https://www.cnblogs.com/www-cnblogs-com-lixuanta/p/15347550.html