题解：P9534 [YsOI2023] 广度优先遍历

koukou · 2026-07-24 15:03:26 · 题解

你考虑什么样的边才会给你带来限制。

非树边中，对于任意一条边 (u,v)，必然有 |dep_u-dep_v|\le 1，不然这条边一定会在搜索的时候被搜到。

然后如果两者深度相同对我们是没有任何影响的，可以直接忽略。

否则，我们设 dep_u+1=dep_v，则 fa_v 必须比 u 先遍历到。这个限制在 LCA 那里需要被处理。

然后把边当作点建边，跑一遍拓扑排序即可。显然其他边放哪里都对我们没有影响。

如果题目要你判无解就是拓扑排序时出现环。

作为一道构造题代码这么长有点恶心了。

:::success[代码]{open}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lg = 20;
const int N = 2e5 + 5;
bool used[N];
vector<int> tr[N], to[N], ord[N];
int n, m, pa[N], dep[N], up[N][lg], in[N], tid[N];
struct edge
{
    int u, v;
}g[N << 1];
int jump(int u, int d)
{
    for(int i = 0; i < lg; i++)
    {
        if(d >> i & 1) u = up[u][i];
    }
    return u;
}
int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    u = jump(u, dep[u] - dep[v]);
    if(u == v) return u;
    for(int i = lg - 1; i >= 0; i--)
    {
        if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
    }
    return up[u][0];
}
int getson(int u, int anc)
{
    return jump(u, dep[u] - dep[anc] - 1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> g[i].u >> g[i].v;
    for(int i = 1; i <= n; i++) cin >> pa[i];
    for(int i = 2; i <= n; i++)
    {
        tr[pa[i]].push_back(i);
        tr[i].push_back(pa[i]);
    }
    queue<int> q;
    q.push(1);
    dep[1] = 0;
    up[1][0] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto v : tr[u])
        {
            if(v == up[u][0]) continue;
            dep[v] = dep[u] + 1;
            up[v][0] = u;
            for(int j = 1; j < lg; j++) up[v][j] = up[up[v][j - 1]][j - 1];
            q.push(v);
        }
    }
    for(int i = 1; i <= m; i++)
    {
        int u = g[i].u, v = g[i].v;
        if(pa[u] == v && !tid[u]) tid[u] = i;
        else if(pa[v] == u && !tid[v]) tid[v] = i;
    }
    for(int i = 1; i <= m; i++)
    {
        int u = g[i].u, v = g[i].v;
        if(dep[u] > dep[v]) swap(u, v);
        if(dep[u] == dep[v]) continue;
        if(dep[v] != dep[u] + 1) continue;
        if(pa[v] == u) continue;
        int p = pa[v];
        int x = lca(u, p);
        int cu = getson(u, x), cp = getson(p, x);
        to[cp].push_back(cu);
        in[cu]++;
    }
    queue<int> que;
    for(int i = 2; i <= n; i++)
    {
        if(in[i] == 0) que.push(i);
    }
    int cnt = 0;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        cnt++;
        ord[pa[u]].push_back(u);
        for(auto v : to[u])
        {
            in[v]--;
            if(in[v] == 0) que.push(v);
        }
    }
    for(int u = 1; u <= n; u++)
    {
        for(auto v : ord[u])
        {
            int id = tid[v];
            cout << g[id].u << " " << g[id].v << "\n";
            used[id] = 1;
        }
    }
    for(int i = 1; i <= m; i++)
    {
        if(!used[i]) cout << g[i].u << " " << g[i].v << "\n";
    }
    return 0;
}

:::