1. 找桥

2. dfs求边双连通分量

e-DCC > 1（没有桥）说明点必在环上

// 找在环路上的点
// e-DCC > 1
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = N * 2;
int idx, n, h[N], ne[M], e[M];
int dfn[N], low[N], num, c[N], dcc;
bool bridge[M]; // 开M
vector<int> V[N];
void add(int a, int b){
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}

void tarjan(int u, int in_edge){
    dfn[u] = low[u] =  ++ num;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(!dfn[j]){
            tarjan(j, i);
            low[u] = min(low[u], low[j]); // 回溯更新

            if(low[j] > dfn[u]) // 不过这条边就到不了更早的点
                bridge[i] = bridge[i ^ 1] = true;
        }
        else if (i != (in_edge ^ 1))
            low[u] = min(low[u], dfn[j]); // 不是来的边就用前面的边更新
    }

}

void dfs(int u){
    c[u] = dcc;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(c[j] || bridge[i]) continue; // 为桥或者已经属于一个区域
        dfs(j);
    }
}

int main(){
    idx = 2;
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b); add(b, a);
    }
    for(int i = 1; i <= n; i ++ )
        if(!dfn[i]) tarjan(i, 0);

    for(int i = 1; i <= n; i ++ )
        if(!c[i]){
            ++ dcc;
            dfs(i);
        }
    for(int i = 1; i <= n; i ++ ){
//        cout << i << " " << c[i] << endl;
        V[c[i]].push_back(i);
    }
    for(int i = 1; i <= dcc; i ++ ){
        if(V[i].size() > 1){
            for(int j = 0; j < V[i].size(); j ++ ) cout << V[i][j] << " ";
        }
    }
    return 0;
}

参考文献

《算法竞赛进阶指南》