lanqiao OJ 108 发现环

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
 
using namespace std ;
const int N = 1e5 +10 ;
struct edge{//用于记录边
  int from , to ;
  edge(int a, int b){
    from = a , to = b ;
  }
};
int n ,cnt;//n是点的数量
bool v[N] ;//记录是否走过这个点
int path[N] ;//最后记录路径
int flag ;//记录一下是否找到环，找到环就退出dfs，要不然死循环
int fa[N] ;//记录每一个节点的前驱节点，便于后面路径的更新
vector<edge> e[N] ;//记录每一条边
 
void dfs(int u ,int pre){
  v[u] = 1 ;//凡是进来的点都标记一下，而且我们每一个点只会走一遍，如果走到第二遍就表示扎到了环
  for(int i = 0 ; i < e[u].size() ; i ++){
    int a = e[u][i].from , b = e[u][i].to ;//起点和终点
    if(b == pre){//因为是无向边所以我们不能再走上一个节点
      continue ;
    }
    fa[b] = a ;//记录一下当前这个点的父节点（前驱节点）
    if(v[b]){//如果找到走了第二次的点，就回溯记录路径
      int tmp = b ;
      flag = 1;//把旗帜标1 ， 表示我们已经找到环了，马上退出dfs
      while(1){
        tmp = fa[tmp];
        path[cnt++] = tmp ;
        if(tmp == b) break ;
      } 
      return  ;
    } 
    else dfs(b,a) ;//没有找到环，继续深搜遍历每一个点
    if(flag == 1) return ;
  }
}
 
int main(){
  cin >> n ;
  for(int i = 0 ; i <n ; i ++){
    int a , b ; cin >> a >> b ;//无向图，所以要记录双向
    e[a].push_back(edge(a,b)) ;
    e[b].push_back(edge(b,a)) ;
  }
 
  dfs(1,0) ;
  sort(path,path + cnt) ;//从大到小排序 
  for(int i = 0 ; i < cnt ; i ++) {
    cout << path[i]<< " "  ;
  }
  cout << endl ; 
  return 0 ;
}