题目链接:https://codeforces.com/problemset/problem/1572/A
大致思路:题目想问的是从头到尾阅读多少次之后,才能读完这本书.
这是一道很套路的拓扑排序的题.看到一个事件有前置条件这种,就应该想到建一个有向无环图然后跑拓扑排序,在这里,我们建立一条从前置条件指向当前页码的有向边.
很容易可以想到当然是从入度为0,即没有前置条件的页码出发开始读.
我们可以开一个二维的小根堆,第一维放需要操作多少次才能做到读这页书,第二维放当前的页码.接下来跑拓扑排序的时候时刻维护第一维的最大值,这个最大值就是满足所有情况的,能把书读完的步骤,也就是我们的答案.之后我们跑拓扑排序的时候,时刻注意判断页码顺序,然后依次维护第一维的操作次数即可.
typedef pair<int,int> PII;
#define maxn 200010
vector<int> vec[maxn];
void solve()
{
int n;
cin>>n;
priority_queue<PII,vector<PII>,greater<PII> > que;
vector<int> in(n+1,0);
for(int i=1;i<=n;i++)
{
vec[i].clear();
}
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
for(int j=1;j<=k;j++)
{
int v;
cin>>v;
vec[v].push_back(i);
in[i]++;
}
}
for(int i=1;i<=n;i++)
{
if(!in[i])
{
que.push({1,i});
}
}
int maxx=0;
vector<int> ans;
while(!que.empty())
{
maxx=max(maxx,que.top().first);
auto u=que.top();
que.pop();
ans.push_back(u.second);
for(auto v:vec[u.second])
{
in[v]--;
if(!in[v])
{
if(v>u.second)
{
que.push({u.first,v});
}
else
{
que.push({u.first+1,v});
}
}
}
}
if((int)ans.size()!=n)
{
cout<<-1<<'\n';
return ;
}
cout<<maxx<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}