蓝桥杯2017年第八届真题-发现环(并查集， DFS）

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int p[N];

bool vis[N] = {false};

vector<int> G[N];

int parent(int x) {

    int res;

    if (x == p[x]) {

        res = x;

    }    

    else {

        res = parent(p[x]);

        p[x] = res;

    }

    return res;

}

void dfs(int a, int b, vector<int> &buf) {

    if (vis[a]) {

        return;

    }

    vis[a] = true;

    buf.push_back(a);

    if (a == b) {

        sort(buf.begin(), buf.end());

        for (int i = 0; i < buf.size(); i++) {

            cout << buf[i] << " ";

        }

        cout << endl;

        return;

    }

    for (int i = 0; i < G[a].size(); i++) {

        dfs(G[a][i], b, buf);

    }

    buf.pop_back();

    vis[a] = false;

}

int main() {

   int n;

   cin >> n;

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

       p[i] = i;

   }

   int a, b;

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

       cin >> a >> b;

       int fA = parent(a);

       int fB = parent(b);

       if (fA == fB) {

           vector<int> buf;

           dfs(a, b, buf);

           break;

       } else {

           p[fB] = fA;

           G[a].push_back(b);

           G[b].push_back(a);

       }

   }

    return 0;

}