蓝桥杯2017年第八届真题-发现环(纯dfs,无并查集)

解题思路:
注意题目说法，如果将1作为根节点，建立一个树，只有一条边沟通树的非父子结点，故而我们可以首先dfs建立树，同时记录父结点，同时再做一遍dfs,此时注意保存沟通非父子节点的边所对应的两个结点。然后我们依照父结点数组追溯出这两个结点的所有祖先，我们同时遍历两个祖先数组，直到遇到一个位置，这个位置的祖先值不一致，从此位置前一个位置后我们记录所有结点，并将其排序后输出。
注意事项:
复杂度O(nlogn),注意祖先结点按祖先层级从低到高记录。
参考代码:

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define maxx 200000
int n,a,b,neww,ans1,ans2;
int fa[maxx];
vector<int> G[maxx];
vector<int> s1,s2;
vector<int> ans;
void dfs(int i)
{

  for(int j=0;j<G[i].size();++j)
  if(fa[G[i][j]]==0)
  {fa[G[i][j]]=i;
  dfs(G[i][j]);}
 
}

void dfs2(int i)
{

  for(int j=0;j<G[i].size();++j)
  {if(fa[G[i][j]]==i) dfs2(G[i][j]);
  else if(fa[i]==G[i][j]) continue;
  else {ans1=i;ans2=G[i][j];}
  }
}

void faa1(int i)
{
  stack<int> ss;
  while(i!=INF)
  {
    ss.push(i);
    i=fa[i];
  }
  while(ss.size()!=0)
  {s1.push_back(ss.top());
  ss.pop();}
 
}

void faa2(int i)
{
  stack<int> ss;
  while(i!=INF)
  {
    ss.push(i);
    i=fa[i];
  }
    while(ss.size()!=0)
  {s2.push_back(ss.top());
  ss.pop();}
  
}

signed main()
{
  cin>>n;
  for(int i=1;i<=n;++i)
  {
    cin>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  fa[1]=INF;
  dfs(1);dfs2(1);
  faa1(ans1);faa2(ans2);
  
  for(neww=0;neww<min(s1.size(),s2.size());++neww)
  {

    if(s1[neww]!=s2[neww])
    {
      --neww;
      break;
    }
  }
  if(neww>=min(s1.size(),s2.size())) --neww;
  for(int i=neww;i<s1.size();++i) ans.push_back(s1[i]);
  for(int i=neww+1;i<s2.size();++i) ans.push_back(s2[i]);
  sort(ans.begin(),ans.end());
  for(int i=0;i<ans.size();++i)
   cout<<ans[i]<<" ";
 
}