P8655 [蓝桥杯 2017 国 B] 发现环 题解

· · 题解

\colorbox{orange}{\color{white}\texttt{题目传送门}}

这道题我第一眼是觉得用Tarjan算法对原图构建一颗dfs树，如果某个顶点可以通过返祖边回到祖先，那答案就是祖先不经过返祖边到达这个顶点经过的所有点。

我们用样例举个例子。

先构建dfs树：

我们发现存在一条非树边 \texttt{(1,3)}，这时我们从 1 号节点开始，依次经过 1,2,5,3 来到 3 号节点，那么如果只看1,2,5,3 节点，就会发现它们原本不构成一个环，而有了 1 到 3 的边，它们就构成了一个环，所以输出 1 2 3 5。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,tim,dfn[200005],low[200005];
int ans,f[100005];
vector<int>g[200005];
void tarjan(int x){
    dfn[x]=low[x]=++tim;
    for(int&i:g[x]){
        if(f[x]==i){//避免程序将(A->B)和(B->A)中的一个判为返祖边
            continue;
        }
        if(!dfn[i]){
            f[i]=x;
            tarjan(i);
            //此处不用取min
        }else{
            low[x]=min(low[x],dfn[i]);
        }
    }
    if(low[x]<dfn[x]){//是返祖边
        int y=x;
        vector<int>ans;
        while(dfn[y]!=low[x]){
            ans.push_back(y);
            y=f[y];
        }
        ans.push_back(y);
        sort(ans.begin(),ans.end());//记得要排序
        for(auto&x:ans){
            cout<<x<<" ";
        }
        exit(0);//退出程序
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);//注意是无向图
    }
    tarjan(1);//其实从任意一个开始都可以，可以根据自己的喜好来
    return 0;
}