【简单图论】CF898 div4 H

Problem - H - Codeforces

题意:

思路:

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

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://uudwc.com/A/edDNo

原文地址:https://blog.csdn.net/weixin_62528401/article/details/133280534

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年10月25日 01:35
kafka各版本消息介绍
下一篇 2023年10月25日 02:35