自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:06:39，当前版本为作者最后更新于2025-02-13 00:56:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Problem Link

题目大意

给定 $n$ 个点 $m$ 条边的 DAG，对于每个 $u$ 求最小的 $i$ 使得保留前 $i$ 条边后 $u$ 的拓扑序唯一。

数据范围：$n\le 2\times 10^5,m\le 8\times 10^5$。

思路分析

首先考虑什么样的 $u$ 拓扑序唯一，即拓扑序小于 $u$ 的点都能到达 $u$，大于 $u$ 的点都能被 $u$ 到达。

考虑第一个条件，只保留拓扑序小等于 $u$ 的点，那么我们要求 $u$ 是唯一一个无出度的点。

同理保留拓扑序大于等于 $u$ 的点，$u$ 是唯一一个无入度的点，这两个条件显然是充要的。

那么动态维护前缀或后缀的导出子图上每个点的最小出边，用堆维护答案即可。

时间复杂度 $\mathcal O(m\log m)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5,MAXM=8e5+5;
int n,m,a[MAXN],deg[MAXN];
struct Edge { int v,w; };
vector <Edge> L[MAXN],R[MAXN];
int f[MAXN],g[MAXN];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i) {
		cin>>u>>v,++deg[v],L[u].push_back({v,i}),R[v].push_back({u,i});
	}
	queue <int> Q;
	for(int i=1;i<=n;++i) if(!deg[i]) Q.push(i);
	for(int i=1;i<=n;++i) {
		int u=a[i]=Q.front(); Q.pop();
		for(auto e:L[u]) if(!--deg[e.v]) Q.push(e.v);
	}
	priority_queue <array<int,2>> S;
	for(int i=n;i>=1;--i) {
		int u=a[i];
		for(auto e:L[u]) if(e.w<g[e.v]) S.push({g[e.v]=e.w,e.v});
		while(S.size()) {
			auto it=S.top();
			if(it[0]!=g[it[1]]) S.pop();
			else { f[u]=max(f[u],it[0]); break; }
		}
		S.push({g[u]=m+1,u});
	}
	priority_queue<array<int,2>>().swap(S);
	for(int i=1;i<=n;++i) {
		int u=a[i];
		for(auto e:R[u]) if(e.w<g[e.v]) S.push({g[e.v]=e.w,e.v});
		while(S.size()) {
			auto it=S.top();
			if(it[0]!=g[it[1]]) S.pop();
			else { f[u]=max(f[u],it[0]); break; }
		}
		S.push({g[u]=m+1,u});
	}
	for(int i=1;i<=n;++i) cout<<(f[i]>m?-1:f[i])<<" \n"[i==n];
	return 0;
}