【拓扑排序】CF1572A Book

分析

这里提供一个比较自然的想法。

首先看到题面，从这些约束关系很容易想到拓扑排序。

接下来我们考虑学会编号为 \(u\) 的章节需要的时间 \(f_u\)，那么答案就是 \(\max f_u\)。

记学会 \(u\)​ 的前驱章节为 \(pre\)​，那么我们有 \(f_u = \max (f_{pre}) + [pre>u]\)。

\([pre>u]\) 代表如果 \(pre>u\) 取 \(1\)，反之取 \(0\)。

// Problem: A. Book
// Contest: Codeforces - Codeforces Round #743 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1572/A
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)

using pii = pair<int, int>;
using ll = long long;

inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=2e5+5, M=N<<1;

struct Edge{
	int to, w, next;
}e[M];

int h[N], tot;

void add(int u, int v, int w){
	e[tot].to=v, e[tot].w=w, e[tot].next=h[u], h[u]=tot++;
}

int n;
int deg[N], f[N];

int bfs(){
	queue<int> q;
	rep(i,1,n) if(!deg[i]) q.push(i);
	rep(i,1,n) f[i]=0;
	
	int cnt=0;
	while(q.size()){
		int u=q.front(); q.pop();
		cnt++;
		
		for(int i=h[u]; ~i; i=e[i].next){
			int go=e[i].to;
			f[go]=max(f[go], f[u]+e[i].w);
			if(--deg[go]==0){
				q.push(go);
			}
		}
	}
	
	if(cnt!=n) return -1;
	return *max_element(f+1, f+1+n)+1;
}

int main(){
	int T; cin>>T;
	while(T--){
		cin>>n;
		rep(i,1,n) h[i]=-1, deg[i]=0;
		tot=0;
		
		rep(i,1,n){
			int k; read(k);
			while(k--){
				int u; read(u);
				add(u, i, u>i);
				deg[i]++;
			}
		}
		
		cout<<bfs()<<endl;
	}	
	return 0;
}