解题思路: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;
}
0.0分
1 人评分