无向图DFS、BFS生成树，ABC251F

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

https://atcoder.jp/contests/abc251/tasks/abc251_f

二、解题报告

1、思路分析

这题就是DFS、BFS生成树的裸题

对于无向图：

1、DFS生成树会囊括所有的横叉边

2、BFS生成树会囊括所有的返祖边

这两个性质均可以通过反证法证明：

1、假设存在 横叉边<u, v> （dfn[u] < dfn[v]）不在DFS生成树上，那么说明搜索到 u 的时候 v已经被搜了，这与 dfn[u] < dfn[v] 矛盾，故原命题成立

2、假设存在 返祖边<u, v> （dep[u] > dep[v] + 1）不在DFS生成树上，那么说明搜索到 u 的时候 v已经被搜了，这与 dep[u] > dep[v] + 1 矛盾，故原命题成立

所以对于两种要求的生成树分别dfs和bfs即可

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

​

#include <bits/stdc++.h> namespace ranges = std::ranges; namespace views = std::views; using i64 = long long; using u32 = unsigned; using u64 = unsigned long long; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, M; std::cin >> N >> M; std::vector<std::vector<int>> adj(N); for (int i = 0; i < M; ++i) { int u, v; std::cin >> u >> v; --u; --v; adj[u].push_back(v); adj[v].push_back(u); } std::vector<std::array<int, 2>> ans; std::vector<bool> vis(N); [&](this auto &&self, int u) -> void { vis[u] = true; for (int v : adj[u]) { if (vis[v]) { continue; } ans.push_back(std::array<int, 2>{u, v}); self(v); } }(0); for (auto &[u, v] : ans) { std::cout << u + 1 << ' ' << v + 1 << '\n'; } assert(ans.size() + 1 == N); std::queue<int> q; ans.clear(); q.push(0); vis[0] = false; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (vis[v]) { ans.push_back(std::array<int, 2>{u, v}); vis[v] = false; q.push(v); } } } assert(ans.size() + 1 == N); for (auto &[u, v] : ans) { std::cout << u + 1 << ' ' << v + 1 << '\n'; } return 0; }