本文主要是介绍Codeforces Round 898 (Div. 4)--H. Mad City--基环树博弈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://codeforces.com/problemset/problem/1873/H
题意：
给定一颗基环树，给定A和B的位置，A追赶B，两人会同时移动，每次一格。
两人的移动
问A是否永远无法追到B。
写在前面：
复习到了拓扑排序，并查集，最短路基本知识！
题解：就是求b点到换上的最小距离与a到该点的距离值大小，b先到则永远追不到！
代码如下：
用拓扑排序找b点到环最近的那个点，并用并查集fa[]记录#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 200005;
#define inf 1e18
#define YES cout<<"YES"<<'\n';
#define NO cout<<"NO"<<'\n';
ll fa[N];
ll find(ll x)
{if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}
void solve()
{ll n,a,b;cin>>n>>a>>b;vector<ll>in(n+1),g[n+1],d(n+1),vis(n+1);ll u,v;for(ll i=1;i<=n;i++){fa[i]=i;d[i]=inf;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);in[v]++;//入度+1in[u]++;}queue<ll>q;for(ll i=1;i<=n;i++){if(in[i]==1) q.push(i);}while(q.size()){ll e=q.front();q.pop();for(auto ed:g[e]){in[ed]--;if(in[ed]==1) q.push(ed);fa[find(e)]=fa[find(ed)];//unionset}}find(b);queue<ll>r;//cout<<fa[b]<<'\n';r.push(fa[b]);d[fa[b]]=0;while(r.size()){ll x=r.front();r.pop();if(vis[x]) continue;vis[x]=1;for(auto ed:g[x]){if(d[x]+1<d[ed]){d[ed]=d[x]+1;r.push(ed);}}}if(d[a]<=d[b]) NOelse YES
}
int main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);ll t;cin>>t;while(t--) solve();return 0;
}拓扑排序：
1 ：从图中选择⼀一个⼊入度为0的顶点,输出该顶点;
2： 从图中删除该顶点及其相关联的弧;
3 ：重复执⾏行1、2直到所有顶点均被输出,拓扑排序完成或者图中再也没有⼊入度为0的顶点(此种情况说明原有向图含有环)。 可以证明,任何一个无环有向图,其全部顶点都可以排成一个拓扑序列。而且其拓扑序列不一定是唯一的。
这篇关于Codeforces Round 898 (Div. 4)--H. Mad City--基环树博弈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
