P11352 题解

· · 题解

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;
}