题解 | 2023 年牛客多校第三场 E 题

题意：给定一张 $G(n,m)G(n,m)$ 的有向图，使用 dfs 算法求解从 $11$ 开始的单源最短路，问给定的图能否在任何边遍历顺序下都正确输出。$1\le n,m\le 10^{5}1\; \backslash le\; n,m\backslash le\; 10^5$。

解法：为什么我们要找支配树？可以考虑以下三个例子：

基本错误型：一个点（$22$）有多种到达方式。

一个环：多次遍历到的点不一定是有重复的。

破环：多种遍历方式会导致破环方式不同（如 $6\to 46\; \backslash to\; 4$，$4\to 24\; \backslash to\; 2$，$5\to 35\; \backslash to\; 3$），从而影响答案。

首先我们依然可以建立一个 bfs 树，找到从 $11$ 出发到每个点的最短距离。然后考虑原图中的每一条边：

1. 如果当前一条边 $(u,v)(u,v)$ 连接的两点是同层的——必然出现了图 1 基本型，因而输出 No。
2. 如果当前一条边 $(u,v)(u,v)$ 连接的两点是 $uu$ 浅 $vv$ 深的——该边会在 bfs 树中用到，且一定满足 ${\mathrm{d}\mathrm{e}\mathrm{p}}_u+1={\mathrm{d}\mathrm{e}\mathrm{p}}_v\{\backslash rm\; dep\}\_u+1=\{\backslash rm\; dep\}\_v$。不关心它对答案的影响。
3. 如果当前一条边 $(u,v)(u,v)$ 连接了不同层的两点（$uu$ 深 $vv$ 浅）——可能出现图 2（正确）或者图 3（错误）的情况。这时要分析从 $11$ 出发是不是必须经过 $vv$ 到 $uu$。如果必须经过，则是图 2 情况。否则，一定可以经过一条不经过 $vv$ 的道路到达 $uu$（支配关系定义），这时更新 $vv$ 的答案会出错（${\mathrm{d}\mathrm{e}\mathrm{p}}_u+1>{\mathrm{d}\mathrm{e}\mathrm{p}}_u>{\mathrm{d}\mathrm{e}\mathrm{p}}_v\{\backslash rm\; dep\}\_u+1\; >\{\backslash rm\; dep\}\_u\; >\; \{\backslash rm\; dep\}\_v$）。因而这个在支配树上维护支配关系即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
namespace dtree // 支配树模板
{
    const int MAXN = 500020;
    vector<int> E[MAXN], RE[MAXN], rdom[MAXN];

    int S[MAXN], RS[MAXN], cs;
    int par[MAXN], val[MAXN], sdom[MAXN], rp[MAXN], dom[MAXN];

    void clear(int n)
    {
        cs = 0;
        for (int i = 0; i <= n; i++)
        {
            par[i] = val[i] = sdom[i] = rp[i] = dom[i] = S[i] = RS[i] = 0;
            E[i].clear();
            RE[i].clear();
            rdom[i].clear();
        }
    }
    void add_edge(int x, int y) { E[x].push_back(y); }
    void Union(int x, int y) { par[x] = y; }
    int Find(int x, int c = 0)
    {
        if (par[x] == x)
            return c ? -1 : x;
        int p = Find(par[x], 1);
        if (p == -1)
            return c ? par[x] : val[x];
        if (sdom[val[x]] > sdom[val[par[x]]])
            val[x] = val[par[x]];
        par[x] = p;
        return c ? p : val[x];
    }
    void dfs(int x)
    {
        RS[S[x] = ++cs] = x;
        par[cs] = sdom[cs] = val[cs] = cs;
        for (int e : E[x])
        {
            if (S[e] == 0)
                dfs(e), rp[S[e]] = S[x];
            RE[S[e]].push_back(S[x]);
        }
    }
    int solve(int s, int *up)
    {
        dfs(s);
        for (int i = cs; i; i--)
        {
            for (int e : RE[i])
                sdom[i] = min(sdom[i], sdom[Find(e)]);
            if (i > 1)
                rdom[sdom[i]].push_back(i);
            for (int e : rdom[i])
            {
                int p = Find(e);
                if (sdom[p] == i)
                    dom[e] = i;
                else
                    dom[e] = p;
            }
            if (i > 1)
                Union(i, rp[i]);
        }
        for (int i = 2; i <= cs; i++)
            if (sdom[i] != dom[i])
                dom[i] = dom[dom[i]];
        for (int i = 2; i <= cs; i++)
            up[RS[i]] = RS[dom[i]];
        return cs;
    }
}
int up[MAXN];
vector<int> G[MAXN];
int dep[MAXN], f[21][MAXN];
void dfs(int x, int fa)
{
    dep[x] = dep[fa] + 1;
    for (int i = 0; i <= 19; i++)
        f[i + 1][x] = f[i][f[i][x]];
    for (auto it : G[x])
    {
        if (it == fa)
            continue;
        f[0][it] = x;
        dfs(it, x);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[f[i][x]] >= dep[y])
            x = f[i][x];
        if (x == y)
            return x;
    }
    for (int i = 20; i >= 0; i--)
        if (f[i][x] != f[i][y])
            x = f[i][x], y = f[i][y];
    return f[0][x];
}
string solve()
{
    int n, m;
    cin >> n >> m;
    dtree::clear(n);
    for (int i = 1; i <= n; i++)
        G[i].clear();
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        dtree::E[x].push_back(y);
    }
    dtree::solve(1, up);
    for (int i = 2; i <= n; i++)
        G[up[i]].push_back(i);
    dfs(1, 0);
    const int inf = 1e9;
    vector<int> dis(n + 1, inf);
    dis[1] = 0;
    queue<int> q;
    q.push(1);
    bool flag = true;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (auto it : dtree::E[x])
            if (dis[it] == inf)
            {
                q.push(it);
                dis[it] = dis[x] + 1;
                continue;
            }
            else if (dis[it] != dis[x] + 1)
            {
                if (lca(it, x) != it)
                    flag = false;
            }
    }
    if (flag)
        return "Yes";
    else
        return "No";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        cout << solve() << "\n";
    return 0;
}