https://www.luogu.org/problemnew/show/P4376

题意：n头牛，给出m个若干头牛的挤奶顺序，求最大的x，使得前m个顺序全部满足，输出字典序最小的方案。

思路：二分x，拓扑排序用bfs，把queue换成堆就行了。

注意dfs实现的拓扑排序不能输出字典序，例如下图：拓扑序应该是12，3，9，4，10，11，6

 

下面的代码在洛谷tle3个点，cf和bzoj都可以ac

有一个比较大的改进是：每次二分其实只需要判环，不需要输出方案，所以在每次二分中直接用queue或者tarjan判环，只在最后输出方案时用优先队列。我懒得写了

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+1000

int n,m;
vector<int> G[maxn],ask[maxn],topo;
int in[maxn];
priority_queue<int,vector<int>,greater<int> > Q;

void input()
{
	int a1,a2;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a1);
		while(a1--)
		{
			scanf("%d",&a2);
			ask[i].push_back(a2);
		}
	}
}

bool toposort()
{
	topo.clear();
	for(int i=1;i<=n;i++)if(in[i]==0)Q.push(i);
	while(!Q.empty())
	{
		int u=Q.top();Q.pop();
		topo.push_back(u); 
		for(int i=0;i<G[u].size();i++)
		{
			int v=G[u][i];
			in[v]--;
			if(in[v]==0)Q.push(v);
		}
	}
	return topo.size()==n;
}

bool check(int mid)
{
	for(int i=1;i<=n;i++)in[i]=0;
	for(int i=1;i<=n;i++)G[i].clear();
	for(int i=1;i<=mid;i++)
	{
		for(int j=0;j<ask[i].size()-1;j++)
		{	
			in[ask[i][j+1]]++;
			G[ask[i][j]].push_back(ask[i][j+1]);
		}
	}
	return toposort();
}

int main()
{
//	freopen("input.in","r",stdin);
	input();
	int l=1,r=m,ans,mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	check(ans);
	for(int i=0;i<n;i++)cout<<topo[i]<<" ";
	cout<<endl;
	return 0;
}