CF1873H - Mad City

知识点：基环树找环

题意

给定一张具有 \(n\) 个点 \(n\) 条边的无向图。现在有两个人，第一个人在 \(a\) 点，第二个人在 \(b\) 点，第一个人要追到第二个人。

两个人每一回合都同时进行操作，要么停留在当前位置，要么走邻接的下一个点。同时，第一个人知道第二个人实时位置。

在两个人的策略都足够优秀的情况下，第二个人是否能够无限制不被第一个人追逐到。

思路

\(n\) 个点 \(n\) 条边的无向图，那么说明这个图是基环树森林。假设两个人不在同一个连通分量，那么两个人一定不会相遇。同时，如果两个人初始位置在同一个位置，那么一定会被追上。

当两个人位于同一个连通分量时，我们就要考虑什么时候第二个人能够一直不被第一个人追上。假设图中有一个两个点以上的环，那么两个人就可以绕着圈转。但是我们要在哪里找到这个环呢？上面有说到这个图是个基环树森林，那么这个连通分量一定为基环树，这个环是一个简单环，那么我们可以使用拓扑排序找一下有哪些点，处于环上。

那么我们考虑两个人如何到达环的问题。

对于第二个人来说，他要到环，一定是走简单路径到达距离他最近的环上的点，这个步骤可以 bfs 计算得到。那么他什么时候无法到达环呢？要么，是第一个人堵在路径上，要么，是第一个人先到第二个人要到达的点。因此，我们只需要判断这两种情况即可。因为第一种情况可以归结于第一个人先跑去目标点堵第二个人，所以我们可以按照两个人的位置各自跑一遍 bfs ，并计算一下目标点是哪个，判断一下第二个人能否先于第一个人到达目标点即可。

实现

#include <bits/stdc++.h>

template <typename T>
constexpr T inf = std::numeric_limits<T>::max() / 2;
using i64 = int64_t;

class DisjointSet {
private:
    std::vector<int> _leader;
    std::size_t _setCount;

public:
    explicit DisjointSet(std::size_t size)
        : _leader(size, -1), _setCount(size) {}

private:
    auto _InRange(int x) const noexcept -> bool {
        return 0 <= x && x < (int)_leader.size();
    }

    auto _GetLeader(int x) -> int {
        if (_leader[x] <= -1) {
            return x;
        }
        return _leader[x] = _GetLeader(_leader[x]);
    }

    auto _GetCount(int x) -> int {
        return -_leader[_GetLeader(x)];
    }

    template <std::strict_weak_order<int, int> _Compare>
    auto _MergeIf(int a, int b, const _Compare &comp) -> bool {
        a = _GetLeader(a);
        b = _GetLeader(b);
        if (!comp(a, b)) {
            std::swap(a, b);
        }
        if (!comp(a, b)) {
            return false;
        }
        _leader[a] += _leader[b];
        _leader[b] = a;
        --_setCount;
        return true;
    }

    auto _MergeTo(int a, int b) noexcept -> bool {
        a = _GetLeader(a);
        b = _GetLeader(b);
        if (a == b) {
            return false;
        }
        _leader[b] += _leader[a];
        _leader[a] = b;
        --_setCount;
        return true;
    }

public:
    auto GetLeader(int x) -> int {
        assert(_InRange(x));
        return _GetLeader(x);
    }

    auto GetCount() const noexcept -> std::size_t {
        return _setCount;
    }

    auto GetCount(int x) -> int {
        assert(_InRange(x));
        return _GetCount(x);
    }

    template <std::strict_weak_order<int, int> _Compare>
    auto MergeIf(int a, int b, const _Compare &comp) -> bool {
        assert(_InRange(a));
        assert(_InRange(b));
        return _MergeIf(a, b, comp);
    }

    auto MergeTo(int a, int b) -> bool {
        assert(_InRange(a));
        assert(_InRange(b));
        return _MergeTo(a, b);
    }

    auto IsSame(int a, int b) -> bool {
        assert(_InRange(a));
        assert(_InRange(b));
        return _GetLeader(a) == _GetLeader(b);
    }

    auto IsSame(std::initializer_list<int> list) -> bool {
        bool ret = true;
        int v = *list.begin();
        for (auto x : list) {
            ret = IsSame(v, x);
            if (!ret)
                break;
        }
        return ret;
    }

    template <typename _Iter>
        requires std::input_iterator<_Iter> &&
                 std::same_as<typename std::iterator_traits<_Iter>::value_type,
                              int>
    auto IsSame(_Iter first, _Iter last) {
        bool ret = true;
        int v = *first;
        for (auto it = first + 1; it != last && ret; ++it) {
            ret = IsSame(v, *it);
        }
        return ret;
    }

    auto Assign(std::size_t size) -> void {
        _leader.assign(size, -1);
        _setCount = size;
    }
};

void Main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    a--;
    b--;

    std::vector adj(n, std::vector<int>{});
    std::vector<int> deg(n);
    DisjointSet dsu(n);
    for (int i = 0; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        deg[u]++;
        deg[v]++;
        dsu.MergeTo(u, v);
    }

    if (!dsu.IsSame(a, b)) {
        std::cout << "YES\n";
        return;
    }
    if (a == b) {
        std::cout << "NO\n";
        return;
    }

    auto TopuSort = [&]() {
        std::queue<int> q;
        for (int i = 0; i < n; i++) {
            if (deg[i] == 1) {
                q.emplace(i);
            }
        }
        while (!q.empty()) {
            int from = q.front();
            q.pop();
            for (auto to : adj[from]) {
                if (--deg[to] == 1) {
                    q.emplace(to);
                }
            }
        }
    };
    TopuSort();

    std::vector<int> list, loop;
    for (int i = 0; i < n; i++) {
        if (dsu.IsSame(i, b)) {
            list.emplace_back(i);
            if (deg[i] >= 2) {
                loop.emplace_back(i);
            }
        }
    }
    if (loop.empty()) {
        std::cout << "NO\n";
        return;
    }

    auto Bfs = [&](int sta) {
        std::vector<int> dis(n, inf<int>);
        std::queue<int> q;
        q.emplace(sta);
        dis[sta] = 0;
        while (!q.empty()) {
            int from = q.front();
            q.pop();
            for (auto to : adj[from]) {
                if (dis[to] == inf<int>) {
                    dis[to] = dis[from] + 1;
                    q.emplace(to);
                }
            }
        }
        return dis;
    };

    auto adis = Bfs(a), bdis = Bfs(b);
    std::ranges::sort(loop, std::less{}, [&](int x) { return bdis[x]; });

    int base = loop.front();
    if (bdis[base] < adis[base]) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int test;
    std::cin >> test;
    for (int i = 0; i < test; i++) {
        Main();
    }
}