做一次拓扑排序,入队条件为度 = 1,结束之后度仍大于1的即为在环上的点。

void top(){
    while(!ts.empty()){
        int k = ts.front();
        ts.pop();
        for(int i : G[k]){
            fd[i]--;
            if(fd[i] == 1){
                ts.push(i);
            }
        }
    }
}

相关题目:
AtCoder Beginner Contest 266 F - Well-defined Path Queries on a Namori
链接: https://atcoder.jp/contests/abc266/tasks/abc266_f

代码:

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

const int N = 2e5 + 10; 
vector<int> G[N];
int d[N];
int fd[N]; 
int cl[N];
int n;
set<int> huan;
queue<int> ts;

void top(){
    while(!ts.empty()){
        int k = ts.front();
        ts.pop();
        for(int i : G[k]){
            fd[i]--;
            if(fd[i] == 1){
                ts.push(i);
            }
        }
    }
}

void dfs(int n, int f, int g){
    for(int i : G[n]){
        if(fd[i] > 1 || i == f) continue;
        cl[i] = g;
        dfs(i, n, g);
    }
}

void pre(){
    for(int i = 1; i <= n; i++){
        if(fd[i] == 1){
            ts.push(i);
            fd[i]--;
        }
    }
    top();

    for(int i = 1; i <= n; i++){
        if(fd[i] > 1) {
            cl[i] = i;
            dfs(i, -1, i);
        }
    }
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        int u,v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
        d[u]++, d[v]++;
        fd[u]++,fd[v]++;
    }

    pre(); 

    int q;
    cin>>q;
    for(int i = 1; i <= q; i++){
        int x,y;
        cin>>x>>y;
        if(cl[x] == cl[y]){
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
}