自动搬运

查看原文

来自洛谷，原作者为

	蒟蒻炒扇贝 唯有沉淀。

搬运于2025-08-24 21:59:30，当前版本为作者最后更新于2021-08-26 11:32:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

核心算法&前置知识：拓扑排序+二分

此题解默认大家已经掌握关于以上算法的基础知识。

同时也默认大家会链式前向星建图点进这题的大佬肯定都会。

Part1：看题+手玩样例

遇到这种具有多种有关优先级条件的题，我们一般首先考虑按照他们的优先顺序进行建图，然后进行拓扑排序。

以本题样例为例，通过FJ的第一次观察结果可知，为奶牛们挤奶的优先级是 $1$ 号奶牛 $>$ $2$ 号奶牛 $>$ $3$ 号奶牛，那我们就考虑建造这一个有向无环图（DAG）（实际上就是条链）：

那么结合FJ第二次观察的结果，优先级是 $4$ 号奶牛 $>$ $2$ 号奶牛，那么我们的图就变成了这样：

如果你用此图来跑拓扑排序的话，那么拓扑序会有两个，分别是 $4\ 1\ 2\ 3$ 和 $1\ 4\ 2\ 3$。

那我们继续来结合FJ第三次观察的结果，此时我们的图变成了这样：

这时候，我们的图出现了环，意味着有几个条件是互相矛盾的，所以此时这张图并没有拓扑序。

既然有环的时候无解，那我们还得判断这个图是否带环，那我们到底该怎么判断呢？

Part2：拓扑排序黑科技：判环

我们以下面的这张有向有环图为例。

我们来按照拓扑排序的流程走一遍：此时我们先删掉入度为 $0$ 的点（也就是 $1$ 号点）， 现在这张图就成这样了：

此时所有的点入度都不为 $0$，也就是说，此时拓扑排序已经进行不下去了（没有任何点可以入队）。

我们知道，当这张图上所有的点都被删去时，拓扑排序才能进行下去，这也侧面说明这张图是一张有向无环图。如果拓扑排序进行不下去时，图上还有点没有被删，那么这张图一定是一张有环的图。

因此，我们只需要在拓扑排序结束之后，判断所有点的入度是否全部为 $0$，如果有不小于 $1$ 个点的入度不为 $0$，则这张图一定有环。

代码：

	queue<int>q;
	for(int i=1;i<=n;i++)
		if(!in[i])
			q.push(i);
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=head[now];i;i=a[i].nxt)
		{
			int to=a[i].v;
			in[to]--;
			if(!in[to])q.push(to);
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++)
		if(!in[i])tot++;
	if(tot<n)return false;
	return true;

那这个时候我们就有了一个非常暴力的思路，既然FJ想要使题目中的 $X$ 尽可能大，那我们就可以从 $[1,M]$ 暴力枚举出 $X$ 的最大大小（通过重新建图+判环），求出 $X$ 之后就可以愉快的用拓扑排序+优先队列来跑出这个答案序列了！

但这样做时间复杂度肯定是爆炸的，这是一个时间复杂度为平方级别的做法。

那我们该怎么优化呢？

Part3：二分

一个显然的结论，如果一张图上有环，那么它无论加上任意数量条边，这张图依然会有环。如果一张图上无环，那么它无论删去任意数量条边，这张图必定没有环。

这不是废话吗。

所以我们发现，定义 $Y\in [1,X)$，定义 $Z\in (X,M]$，如果 $X$ 符合要求，那么 $Y$ 也必定符合要求。同样，如果$X$不符合要求，那么 $Z$ 也必定不符合要求。

这便说明，求 $X$ 的这个过程可以用二分来实现。

那这样我们就实现了这份暴力代码的优化。

Part4：完整代码

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=1e5+5;
int n,m,cnt,head[MAXN],in[MAXN];
vector<int>v[MAXN];
struct edge
{
	int v,nxt;
}a[MAXN*2];
void addedge(int u,int v)
{
	a[++cnt].v=v;
	a[cnt].nxt=head[u];
	head[u]=cnt;
}
void build(int x)
{
	cnt=0;
	memset(head,0,sizeof(head));
	memset(in,0,sizeof(in));
	for(int i=1;i<=x;i++)
	for(int j=0;j<v[i].size()-1;j++)
	{
		addedge(v[i][j],v[i][j+1]);
		in[v[i][j+1]]++;
	}
}
int check(int x)
{
	build(x);
	queue<int>q;
	for(int i=1;i<=n;i++)
		if(!in[i])
			q.push(i);
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=head[now];i;i=a[i].nxt)
		{
			int to=a[i].v;
			in[to]--;
			if(!in[to])q.push(to);
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++)
		if(!in[i])tot++;
	if(tot<n)return false;
	return true;
}
void get_ans(int x)
{
	build(x);
	priority_queue<int,vector<int>,greater<int> >q;//使用优先队列 保证这个拓扑序的字典序最小
	for(int i=1;i<=n;i++)
		if(!in[i])
			q.push(i);
	while(!q.empty())
	{
		int now=q.top();
		q.pop();
		cout<<now<<" ";
		for(int i=head[now];i;i=a[i].nxt)
		{
			int to=a[i].v;
			in[to]--;
			if(!in[to])q.push(to);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int si;
		cin>>si;
		for(int j=1;j<=si;j++)
		{
			int x;
			cin>>x;
			v[i].push_back(x);
		}
	}
	int l=1,r=m;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	int ans;
	for(ans=r;ans<=l;ans++)if(check(ans))break;
	get_ans(ans);
	return 0;
}

Part5：P.S.

快速将图删除的方法：将 $head$ 数组中的数值全部重置为 $0$，并且将 $cnt$ 归 $0$。

二分时不知道 $l$ 是正确答案还是 $r$ 是正确答案？二分结束后用这几行代码：

	int ans;
	for(ans=r;ans<=l;ans++)if(check(ans))break;

这样即可求出本次二分的正确答案。感觉有点暴力实际上跑的还是很快的，因为二分过后 $l-r$ 的值非常小。