蓝桥杯2017年第八届真题-发现环-题解（C++代码）

解题思路:DFS不断向当前结点的下一个结点前进，顺便记下下一个结点的父节点以便回头可以找到所有在环上的结点。用一个数组s[maxn]记录DFS过程中每一个结点的访问状态，对于结点p, 如果：s[p]=-1代表当前结点正在访问中；s[p]=0代表当前未被访问；s[p]=1代表当前结点已经被访问过了。如果在DFS过程中发现当前结点的s[p]=-1代表该结点位于环上，通过父节点回头找就可以找到所有在环上的结点。

注意事项:1.初始结点的父节点初始化为它自己。2.DFS的过程中不要回头找。

参考代码:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

const int maxn = 100000 + 5;

int s[maxn], fa[maxn];

vector<vector<int> > G(maxn);

vector<int> ring;

bool dfs(int p) {

    if (s[p] < 0) {

        int t = p;

        while (fa[t] != p) {

            ring.push_back(t);

            t = fa[t];

        }

        ring.push_back(t);

        return true;

    }

    if (!s[p]) {

        s[p] = -1;

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

            if (G[p][i] != fa[p]) {

                fa[G[p][i]] = p;

                if (dfs(G[p][i])) {

                    return true;

                }

                fa[G[p][i]] = 0;

            }

        }

        s[p] = 1;

        return false;

    }

    else {

        return false;

    }

}

int main() {

    int N = 0;

    cin >> N;

    int a = 0, b = 0;

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

        cin >> a >> b;

        G[a].push_back(b);

        G[b].push_back(a);

    }

    fa[1] = 1;

    dfs(1);

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

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

        cout << ring[i] << ' ';

    }

    return 0;

}