c++利用数组记录路径

解题思路:使用一个bool已经dfs来判断环上点的位置，详细的看代码上的注释

注意事项:

参考代码:

#include<bits/stdc++.h>

#define DZT ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define int long long

using namespace std;

const int N =1e5+5;

bool ed[N],flag;//ed数组用记录该店是否来过 flag用来判断是否发现了环

int fa[N];

vector<int> m[N];

vector<int> ans;

int n,k;//k表示找到了环的一个节点

void dfs(int now,int f){

    fa[now]=f;//利用fa数组来记录路径

    if(ed[now]){flag=true;k=now; return;}

    ed[now]=true;

    for(int i:m[now]){

        if(flag){return;}//已经发现了环上的点了就没有必要继续后面的搜索了

        if(i==f) continue;

        dfs(i,now);

    }

}

signed main()

{   

    DZT//别在意这个

    cin>>n;

    for(int i=1;i<=n;i++){

        int x,y; cin>>x>>y;

        m[x].push_back(y);

        m[y].push_back(x);

    }

    dfs(1,0);

    int t=k;

    while(fa[t]!=k){//将路径上的点保存到ans中

        ans.push_back(t);

        t=fa[t];

    }

    ans.push_back(t);//记住别漏了一个

    sort(ans.begin(),ans.end(),less<int>());//排序一下

    for(int i:ans){

        cout<<i<<" ";

    }

    return 0;

}