[ABC251F] Two Spanning Trees
Left_i_Forever
·
·
题解
题目传送门
2025.2.6 应读者要求，补充一下证明。
题目大意
给定一个无向图 G，其中有 n 个点，m 条边，构造两棵生成树 T_1 和 T_2 满足：
思路
最开始没思路，于是把样例的图画下来，不难发现 T_1 就是深搜的路径，而 T_2 就是广搜的路径。
考虑反证，先看 T_1，如果一条非树边连接的两个点树上不是祖宗关系，则从 dfn 序小的一点出发，必然需要回溯才能到达另一点，但是实际上可以直接从这条边到达，所以矛盾。
所以我们可以直接通过广搜和深搜解决这个问题。
## code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector <int> v[N];
bool vis[N];
void dfs(int u)
{
vis[u] = true;
for (int i = 0; i < v[u].size(); i++)
{
int j = v[u][i];
if (vis[j]) continue;
cout << u << " " << j << endl;
dfs (j);
}
}
queue <int> q;
void bfs()
{
q.push (1);
vis[1] = true;
while (q.size())
{
int x = q.front();
q.pop();
for (int i = 0; i < v[x].size(); i++)
{
int j = v[x][i];
if (vis[j]) continue;
vis[j] = true;
cout << x << " " << j << endl;
q.push (j);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
v[x].push_back (y);
v[y].push_back (x);
}
dfs (1);
memset (vis, false, sizeof vis);
bfs ();
return 0;
}
```