关于基环树的环可以使用拓扑排序来解决
在基环树中,只有唯一的环在拓扑排序后入度任然为2。所以使用拓扑排序来标记,未被标记的点就是环上的点。
P8655 [蓝桥杯 2017 国 B] 发现环 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
#define si set<int>
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define pb(x) push_back(x);
#define fi first
#define sc second
#define is insert
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
const int INF =1e18;
const int N = 1e5+10;
int in[N],st[N];
vector<int> v[N];
int n;
void top()
{
queue<int> q;
for (int i=1;i<=n;i++){
if(in[i]==1){
q.push(i);
st[i]=1;
}
while(q.size()){
int tmp=q.front();
q.pop();
for (auto it : v[tmp]){
in[it]--;
if(in[it]==1){
q.push(it);
st[it]=1;
}
}
}
}
}
void print()
{
for (int i=1;i<=n;i++){
if(!st[i]){
cout<<i<<" ";
}
}
}
signed main()
{
IOS
//.........................//
cin>>n;
//memset(h,-1,sizeof h);
for (int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
v[x].pb(y);
v[y].pb(x);
in[x]++;
in[y]++;
}
top();
print();
//return 1;
}