【简单图论】CF898 div4 H-Toy模板网

这篇具有很好参考价值的文章主要介绍了【简单图论】CF898 div4 H。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Problem - H - Codeforces

题意：

【简单图论】CF898 div4 H,图论,图论

思路：

手玩一下样例就能发现简单结论：

v 离它所在的树枝的根的距离 < m 离这个根的距离时是 YES

否则就是NO

实现就很简单，先去树上找环，然后找出这个根，分别给a 和 b BFS一遍，得出两个dis数组，比较一下即可

对于只有的环情况和 m = v 的情况需要特判

Code：

#include <bits/stdc++.h>

constexpr int N = 2e5 + 10;
constexpr int M = 1e6 + 10;
constexpr int Inf = 1e9;

std::queue<int> q1, q2;
std::vector<int> adj[N];

int n, a, b;
int top = 0;
int u[N], v[N];
int st[N], r[N];
int dis1[N];
int dis2[N];

int find_r(int u, int fa) {
    if (st[u]) return u;
    st[u] = 1;
    for (auto v : adj[u]) {
        if (v == fa) continue;
        int t = find_r(v, u);
        if (t) {
            r[++ top] = u;
            st[u] = 2;
            return t == u ? 0 : t;
        }
    }
    return 0;
}
void bfs1(int u) {
    memset(dis1, 0x3f, sizeof(dis1));
    dis1[u]= 0;
    q1.push(u);
    while(!q1.empty()) {
        int u = q1.front();
        q1.pop();
        for (auto v : adj[u]) {
            if (dis1[v] > dis1[u] + 1) {
                dis1[v] = dis1[u] + 1;
                q1.push(v);
            }
        }
    }
}
void bfs2(int u) {
    memset(dis2, 0x3f, sizeof(dis2));
    dis2[u] = 0;
    q2.push(u);
    while(!q2.empty()) {
        int u = q2.front();
        q2.pop();
        for (auto v : adj[u]) {
            if (dis2[v] > dis2[u] + 1) {
                dis2[v] = dis2[u] + 1;
                q2.push(v);
            }
        }
    }
}
void solve() {
    std::cin >> n >> a >> b;
    top = 0;
    while(!q1.empty()) q1.pop();
    while(!q2.empty()) q2.pop();
    for (int i = 1; i <= n; i ++) {
        st[i] = 0;
        adj[i].clear();
    }
    for (int i = 1; i <= n; i ++) {
        std::cin >> u[i] >> v[i];
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    if (a == b) {
        std::cout << "NO" << "\n";
        return;
    }
    find_r(1, 0);
    bfs1(b);
    int miu1 = Inf, ansu = 0;
    for (int i = 1; i <= n; i ++) {
        if (st[i] == 2 && miu1 > dis1[i]) {
            miu1 = dis1[i];
            ansu = i;
        }
    }
    if (st[b] == 2) {
        std::cout << "YES" << "\n";
        return;
    }
    bfs2(a);
    int ans1 = dis2[ansu];
    int ans2 = miu1;
    if (ans1 > ans2) std::cout << "YES" << "\n";
    else std::cout << "NO" << "\n";
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while(t --) {
        solve();
    }
    return 0;
}

文章来源地址https://www.toymoban.com/news/detail-727139.html

到了这里，关于【简单图论】CF898 div4 H的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！