php简单购物网站源码,学网站开发培训班,个人简历模板空白表格,高级网站建设费用题目链接#xff1a;Problem - H - Codeforces
题目大意#xff1a;给定一个带环的图#xff0c; 以及a, b两点 判断再图上不断的移动#xff0c; b想不与a相遇#xff0c; a想捉到b, 并且二者只能移动一步。 若b跑不掉 NO 否则YES.
具体题目看链接
输入#xff1a;
…题目链接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.
#includebits/stdc.h
using namespace std;using i64 long long;
using i128 __int128;void solve(){int n, a, b;cin n a b;vectorint d(n1);vectorvectorint g(n1);for(int i0; in; i) {int u, v;cin u v;d[u], d[v];g[u].push_back(v);g[v].push_back(u);}if(ab){//特判cout NO\n;return;}queueint q;int p b;for(int i1; in; 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(up) {//删点时不断靠近环p v;}}}setint st;for(int i1; in; 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;vectorint vis(n1,0);//dfs搜索距离auto dfs [](autodfs, int u,int len)-void{if(ua || ub){if(ua) {dis1 min(len, dis1);}if(ub) {dis2 min(len, dis2);}return;}vis[u] 1; for(int v : g[u]) {if(vis[v]0) {dfs(dfs, v, len1);}}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();}
} 欢迎各位点赞与观看 欢迎大佬指正。
