H. Mad City
题意：b能否不被a抓到。
题解：这是基环树，只要b先与a在环上，b就永远也不会被抓到。
所以，此题就是求a，b到环上的距离，如果有一点b到环上的距离小于a，那么就永远也不会被抓到。
比较简单的找环的方式就是利用拓扑排序，然后就是最短路径的模板了（利用简单的bfs或者dfs就行）。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int h[N], to[2 * N], ne[2 * N],cnt;
void add(int x, int y) {
to[++cnt] = y;
ne[cnt] = h[x];
h[x] = cnt;
}
int d1[N],vis[N];
void bfs1(int u) {//求a到各点的距离
memset(d1, 0x3f, sizeof d1);
memset(vis, 0, sizeof vis);
queue<int> q;
q.push(u);
d1[u] = 0;
while (q.size()) {
int x = q.front(); q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = h[x]; i; i = ne[i]) {
int v = to[i];
if (vis[v]) continue;
d1[v] = min(d1[v], d1[x] + 1);
q.push(v);
}
}
}
int d2[N],vis1[N];
void bfs2(int u) {//求b到各点距离
memset(d2, 0x3f, sizeof d2);
memset(vis1, 0, sizeof vis1);
queue<int> q;
q.push(u);
d2[u] = 0;
while (q.size()) {
int x = q.front(); q.pop();
if (vis1[x]) continue;
vis1[x] = 1;
for (int i = h[x]; i; i = ne[i]) {
int v = to[i];
if (vis1[v]) continue;
d2[v] = min(d2[v], d2[x] + 1);
q.push(v);
}
}
}
int n, a, b;
int ind[N];
void bfs() {//拓朴排序，找环
queue<int> q;
for (int i = 1; i <= n; i++) {
if (ind[i] == 1) q.push(i);
}
while (q.size()) {
int u = q.front(); q.pop();
for (int i = h[u]; i; i = ne[i]) {
int v = to[i];
if (--ind[v] == 1) {
q.push(v);
}
}
}
}
void sovle() {
memset(ind, 0, sizeof ind);
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
add(x, y);
add(y, x);
ind[y]++;
ind[x]++;
}
if (a == b) {
cout << "No\n";
return;
}
bfs();//拓扑排序
bfs1(a);
bfs2(b);
for (int i = 1; i <= n; i++) {
if (ind[i] > 1) {
if (d2[i] < d1[i]) {
cout << "YES\n";
return;
}
}
}
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
memset(h, 0, sizeof h);
cnt = 0;
sovle();
}
return 0;
}