ABC266F 题解

输入的图是一颗基环树。

对于 \(x,y\)，如果把环上的边去掉，得到的森林里 \(x,y\) 仍然在同一颗树内，那么显然只有一条路。

否则一定要经过环，有两条路。

于是 dfs 或着拓扑排序找环即可。

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

const int N = 2e5 + 5;
int deg[N], n;
vector<int> e[N];
int id[N];
bool vis[N];

void dfs(int x, int fa)
{
    for(int i : e[x])
    {
        if(i == fa || !vis[i]) continue;
        id[i] = id[x];
        dfs(i, x);
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int x, y; cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
        deg[x] ++, deg[y] ++;
    }
    queue<int> q;
    for(int i = 1; i <= n; i ++)
        if(deg[i] == 1) q.push(i), vis[i] = 1;
    while(q.size())
    {
        int t = q.front(); q.pop();
        for(int i : e[t])
        {
            if(!vis[i] && --deg[i] == 1)
                q.push(i), vis[i] = 1;
        }
    }
    for(int i = 1; i <= n; i ++)
        if(!vis[i]) id[i] = i, dfs(i, 0);
    int Q; cin >> Q;
    while(Q --)
    {
        int x, y; cin >> x >> y;
        cout << ((id[x] == id[y]) ? "Yes\n" : "No\n");
    }

    return 0;
}