H. Mad City

题目链接：Problem - H - Codeforces

题目大意：给定一个带环的图， 以及a, b两点 判断再图上不断的移动， b想不与a相遇， a想捉到b, 并且二者只能移动一步。 若b跑不掉 NO 否则YES.

具体题目看链接

输入：

第一行包含一个整数 t (1≤t≤1000 ) - 测试用例数。

每个测试用例的第一行包含三个空格分隔的整数 n , a , b ( 3≤n≤2⋅1e5 ；( 3≤n≤2⋅1e5 ; 1≤a,b≤n )--

下面的 n 行分别包含两个整数 ui , vi .( 1≤ui,vi≤n, ui≠vi )-- ui 和 vi 之间有一条道路。

所有测试用例中 n 的总和不超过 2⋅1e5 。

保证有环.

解题思路： 通过题目信息， 判断两个点是否肯定会相遇

1.若两个点在环上，那么一定不会相遇，可直接输出YES.

2.该题考察基环树， 当b不在环上时，那么若a点还想与b点相遇， 只有在b点未进入环时堵住b进入环的入环点。所以判断b点到进入环的入点的距离 与 入环点到a点的距离，设入环点为p点。 则需判断  pa <= pb 是NO, 否则 YES.

3.做法， 由于基环树， 要用到拓朴排序， 去掉枝丫， 先判断b点是否在环里。 若不在，则需要做dfs, 搜索出pa, pb的距离。 而p点的求法， 在拓朴排序是删掉该点p时就更新p点的下一个点为p.机p == u 时， p = v.即可找出在环上离b点最近的点p.

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;

void solve(){
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> d(n+1);
    vector<vector<int>> g(n+1);
    for(int i=0; i<n; i++) {
        int u, v;
        cin >> u >> v;
        d[u]++, d[v]++;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(a==b){//特判
        cout << "NO\n";
        return;
    }
    queue<int> q;
    int p = b;

    for(int i=1; i<=n; i++) {
        if(d[i]==1) {
            q.push(i);
        }
    }
    //拓朴排序找里b点最近的环上点
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        d[u]--;
        for(int v : g[u]) {
            if(d[v]==0)continue;
            d[v]--;
            if(d[v]==1) {
                q.push(v);
            }
            if(u==p) {//删点时不断靠近环
                p = v;
            }
        }
    }

    set<int> st;
    for(int i=1; i<=n; i++) {
        if(d[i] >= 2) {
            st.insert(i);
        }
    }
    //判断b是否再环上
    if(st.contains(b)) {
        cout << "YES\n";
        return;
    }
    
    int dis1 = INT_MAX/2, dis2 = INT_MAX/2;
    vector<int> vis(n+1,0);
    //dfs搜索距离
    auto dfs = [&](auto&&dfs, int u,int len)->void{
        if(u==a || u==b){
            if(u==a) {
                dis1 = min(len, dis1);
            }
            if(u==b) {
                dis2 = min(len, dis2);
            }
            return;
        }
        vis[u] = 1; 
        for(int v : g[u]) {
            if(vis[v]==0) {
                dfs(dfs, v, len+1);
            }
        }
        vis[u] = 0;//再图上搜索，记得回溯
    };
    
    dfs(dfs, p, 0);
    if(dis1 <= dis2) {//最后的判断
        cout << "NO\n";
    }else{
        cout << "YES\n";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}

 欢迎各位点赞与观看， 欢迎大佬指正。