P9534 [YsOI2023] 广度优先遍历

Hanghang007 / 2023-08-14 / 原文

好题。

首先考虑到对于任意的边的输入顺序，分层图是不会变的，即所有点到根的最短距离不变。

那么分为两种边，分别为不同层的边相连，相同层的边相连。

显然第二种边是无用的，我们将其放到最后输出即可。

由于下层的决策会影响上层的决策而且不同层之间的边的顺序不会影响答案，所以我们按分层图从大到小处理。

不妨设当前层为 $t$，那么上一层为 $t-1$，对于连接不同层的边，层数大的儿子，小的为父亲,节点 $x$ 的真父亲是 $ba_x$，$t-1$ 到 $t$ 的边的顺序只有两种因素决定：$t$ 层的点的相对顺序，以及 $t$ 层的点 $x$ 所有父亲的相对关系。

对于第一种情况，显然对于每个点都要被真父亲选走，所以 $ba_x$ 要在其他父亲之前。

对于第二种情况，一种暴力的做法是枚举 $t$ 层任意两点 $x,y$，如果 $x$ 要在 $y$ 之前，那么 $ba_x$ 也一定要在 $ba_y$之前。

由于答案一定存在，那么每一层的相对关系一定由多个 $DAG$ 组成，我们对每个点赋值 $p$，那么如果 $x$ 在 $y$ 之前，那么 $p_x$ 一定比 $p_y$ 小。

这里存在一个问题，有可能对于两个不同 $DAG$ 的点，$p$ 值也会存在一个相对关系，但在原图中这是没有的，所以我们要再建立并查集，维护每个 $DAG$ 里面的节点。

那么我们对同层的边排序的时候，先考虑并查集祖先，然后考虑父亲的权值，再考虑儿子的权值。

可是这个是 $\sum d^2 + e log{e}$ 的算法，$d$ 为每层的点数，$e$ 为两层间的边数，不排除能过 $1e5$。

考虑优化，发现此题的瓶颈在于要枚举 $t$ 层的任意两点来推出 $ba_x$ 的相对关系。

由于题目保证存在答案，那么我们可以想办法直接继承儿子的权值 $p$。

那么我们可以直接继承所有儿子里面最小的权值，那么我们对于任意值大于 $p$ 的点且在同一并查集祖先的都可以直接得到相对顺序。

那这样就做完了。复杂度 $n+m \log m$。

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e6+3;
int n,m,k,dep[N],f[N],p[N],ba[N],in[N];
vector<int>ve[N],pos[N],g[N];
vector<pii>res[N];
bool v[N],vis[N];
struct Nod{int x,y;}a[N];
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
#define fi first
#define se second
bool Cmp(pii a,pii b)
{
    if(F(a.fi)==F(b.fi))
    {
        if(p[a.fi]!=p[b.fi])return p[a.fi]<p[b.fi];
        return p[a.se]<p[b.se];
    }
    return F(a.fi)<F(b.fi);
}
void Bfs()
{
    queue<int>q;q.push(1);memset(dep,-1,sizeof(dep));dep[1]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int y:ve[x])if(dep[y]==-1)dep[y]=dep[x]+1,q.push(y);
    }
    for(int i=1;i<=n;i++)pos[dep[i]].push_back(i),k=max(k,dep[i]);
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++)cin>>x>>y,ve[x].push_back(y),ve[y].push_back(x);
    for(int i=1;i<=n;i++)cin>>ba[i],f[i]=i;
    Bfs();
    for(int t=k;t>1;t--)
    {
        for(int x:pos[t])p[ba[x]]=!p[ba[x]]?p[x]:min(p[ba[x]],p[x]),f[F(ba[x])]=F(x);
        for(int x:pos[t])for(int y:ve[x])if(dep[y]==t-1&&y!=ba[x])
            g[ba[x]].push_back(y),in[y]++,f[F(y)]=F(ba[x]);
        queue<int>q;
        for(int x:pos[t-1])if(!in[x])q.push(x),v[x]=1;
        while(!q.empty())
        {
            int x=q.front();q.pop();
            for(int y:g[x])if(!v[y])
            {
                p[y]=max(p[y],p[x]+1);
                if(!(--in[y]))q.push(y),v[y]=1;
            }
        }
        for(int x:pos[t])for(int y:ve[x])if(dep[y]==t-1)
            res[t-1].push_back(make_pair(y,x));
        sort(res[t-1].begin(),res[t-1].end(),Cmp);
    }
    for(int i=1;i<k;i++)for(int j=0;j<res[i].size();j++)
        cout<<res[i][j].fi<<" "<<res[i][j].se<<endl;
    for(int t=1;t<=k;t++)for(int x:pos[t])for(int y:ve[x])
        if(dep[y]==t&&x<y)cout<<x<<" "<<y<<endl;
    return 0;
}