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();}
}

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