环环环！！！！！！！！

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<vector>
  4 #include<cstring>
  5  
  6 using namespace std;
  7  
  8 const int N = 100000+5;
  9  
 10 vector<int> V[2*N];
 11 int parent[N], S, E, n;
 12 int vis[N] = {0};
 13  
 14 void init()
 15 {
 16     for(int i=0; i<=N; i++){
 17         parent[i] = i;
 18     }
 19     
 20 }
 21  
 22 int Find(int a)
 23 {
 24     return parent[a] == a? a : (parent[a] = Find(parent[a]));
 25 }
 26  
 27 bool Union(int a, int b)
 28 {
 29 //    cout << a << "    par  " << b << endl;
 30     a = Find(a);
 31     b = Find(b);
 32     
 33     if(a == b){//已构成环 
 34         return true;
 35     }
 36     else {
 37         parent[a] = b;
 38         return false;
 39     }
 40 } 
 41  
 42 void dfs(int u)
 43 {
 44 //        cout << u << E <<endl;
 45         
 46         if(u == E){//到达终点
 47         //    cout<< n << "输出结果为:" ; 
 48             for(int i=1; i<=n; i++){
 49         //        cout << i << ":" << vis[i] << endl;
 50                 if(vis[i]){
 51                     cout << i;
 52                     printf((i == n) ? "\n" : " ");
 53                     //cout << ((i==n) ? endl : " ");
 54                 }
 55             } 
 56             return;
 57         }
 58     //    else cout << u << "!=" << E << endl;
 59         
 60         for(int i=0; i<V[u].size(); i++){
 61             int next = V[u][i];
 62             if(vis[next] == 0){
 63                 vis[next] = 1;
 64                 dfs(next);
 65                 vis[next] = 0;
 66             }
 67         }
 68     return;
 69 }
 70  
 71 int main()
 72 {
 73     cin >> n;
 74     
 75     init();
 76     
 77     for(int i=0; i<n; i++){
 78         int u, v;
 79         
 80         cin >> u >> v;
 81 //            cout << u <<  "  init   " << v << endl;
 82         if(Union(u, v)){//已构成环 
 83         
 84              S = u, E = v;
 85              break;
 86         }
 87         else {
 88             V[u].push_back(v);
 89             V[v].push_back(u);
 90         }
 91     }
 92     
 93 //    cout << "start:" << S << "    end:" << E << endl;
 94     
 95     vis[S] = 1; 
 96     dfs(S);
 97  
 98     return 0;
 99 
100 }