题目描述：
给出一个有 $N$ 个结点的树，添加一条边之后出现了环，找出环上的所有节点，从小到大输出。
数据范围：
$1\le N \le 10^5$
题解：
基环树，只有一个环，有链连在环上的连通图。
需要对无向图进行遍历检测环，出现环之后把环上的点都记录下来，排序，输出。
无向图不需要使用节点的访问状态了，因为不会存在类似有向图这样的情况。
因此只需要使用 $vis[i]=0/1$ 表示访问过与否即可。
有向图需要使用 $vis[i]=0/1/2$ 表示未访问过，访问中（在遍历栈中），访问过（已经出栈），当遇到 $vis[i]=1$ 说明出现了环路，这时需要记录答案。
需要类似回溯使用一个栈记录当前访问路径上的元素，需要回溯。使用一个vector应该会更好，在记录答案时不要弹栈，直接倒着遍历vector把节点记录下来即可。避免在此处弹栈之后，回溯的时候继续弹栈会出现栈空继续弹栈的情况。
图的遍历，一般前序和后序比较重要，类似回溯算法，但是有不同。回溯由于搜索树根节点是个空节点，边代表的是执行的操作，因此打标记回溯等操作应该放到for循环内部；图的遍历只需要按照前序，后序遍历的方式，打标记回溯等需要放在刚进入该节点与离开该节点处，因此需要放在for循环外部。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
vector<int> g[maxn];
bool vis[maxn] = {};
bool hasCircle = false;
stack<int> st;
vector<int> ans;
void dfs(int u, int fa)
{
if (vis[u])
{
hasCircle = true;
while (st.size() && st.top() != u)
{
ans.emplace_back(st.top());
st.pop();
}
ans.emplace_back(u);
return;
}
if (hasCircle)
return;
vis[u] = true;
st.push(u);
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v == fa)
continue;
dfs(v, u);
}
if (st.size())
st.pop();
vis[u] = false;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0, u, v; i < n; ++i)
{
cin >> u >> v;
u--;
v--;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs(0, -1);
sort(ans.begin(), ans.end());
for (auto &u : ans)
{
cout << u + 1 << " ";
}
return 0;
}
|