题目链接
题目描述
小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？

题解：

问题是求出图中的环，并顺序输出环中元素
有两个方法可以做：
第一个是用拓扑排序法，点度数为1的肯定不在环内，如果与度为1的点相连的边-1后度也是1的话肯定也不是
最后没有被标记的点就是答案
还一个方法是用并查集+dfs
用并查集对不同块的点进行连接，如果发现两个点已经在一个块内，说明这两个点在环上，那么就拿一个点作为起点一个点作为终点，dfs遍历顺序输出即可

代码：

#include<bits/stdc++.h>
#define x first
#define y second
#define mem(h) memset(h,-1,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
   
    inline LL read(){
   
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){
   o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
//#############以上是自定义技巧（可忽略）########## 
const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131;
int h[N],e[M],ne[M],idx;
int d[N];
bool st[N];
int n;
void add(int a,int b){
   
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topo(){
   
    queue<int>q;
    for(int i=1;i<=n;i++){
   
        if(d[i]==1){
   //把所有度为1的点放去队列
            q.push(i);
            st[i]=1;
        }
    }
    while(!q.empty()){
   
        int u=q.front();q.pop();
        for(int i=h[u];~i;i=ne[i]){
   
            int j=e[i];
            if(st[j])continue;
            if(--d[j]==1){
   //如果与度为1的点相连的边-1后度也是1的话，那么加入队列
                q.push(j);
                st[j]=1;
            }
        }
    }
}
int main(){
   
    mem(h);
    cin>>n;
    for(int a,b,i=0;i<n;i++){
   
        cin>>a>>b;
        add(a,b),add(b,a);//建边
        d[a]++,d[b]++;//度+1
    }
    topo();//拓扑排序
    for(int i=1;i<=n;i++){
   
        if(!st[i])cout<<i<<" ";
    }
    return 0;
}

#include<bits/stdc++.h>
#define x first
#define y second
#define mem(h) memset(h,-1,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
   
    inline LL read(){
   
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){
   o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
//#############以上是自定义技巧（可忽略）########## 
const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131;
int h[N],e[M],ne[M],idx;
int ans[N];
bool st[N];
int fa[N];
int n;
int sx,ex;
void add(int a,int b){
   
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int find(int x){
   
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void dfs(int x,int cnt){
   //x表示当前点，cnt表示当前答案下标
    ans[cnt]=x;//当前答案下标放x点
    if(x==ex){
   //如果已经到达最终点
        sort(ans,ans+cnt+1);//就把答案排序
        for(int i=0;i<=cnt;i++){
   
            cout<<ans[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    st[x]=1;//标记已经来过
    for(int i=h[x];~i;i=ne[i]){
   //搜索相邻的的点
        int j=e[i];
        if(st[j])continue;
        dfs(j,cnt+1);
    }
    st[x]=0;
}
int main(){
   
    mem(h);
    cin>>n;
    for(int i=0;i<=n;i++)fa[i]=i;
    int a,b;
    for(int i=0;i<n;i++){
   
        cin>>a>>b;
        if(find(a)!=find(b)){
   //如果不在一个集合就合并，并建边
            fa[find(a)]=find(b);
            add(a,b),add(b,a);
        }else{
   
            sx=a,ex=b;//如果在一个集合就证明两个点在环里，一个作为起始点，一个作为最终点
        }
    }
    dfs(sx,0);
    return 0;
}