算法
(BFS树) $O(N + M)$
通过上图可以看出,这正是 BFS树
的结构,所以我们直接用 $\rm BFS$ 来搜即可。
注意:在图上 $\rm BFS$ 的过程中,除了 dist
数组外,还需要开 pre
数组,用来记录当前节点的上个节点。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
const int INF = 1001001001;
vector<int> to[100005];
int main() {
int n, m;
cin >> n >> m;
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
queue<int> q;
vector<int> dist(n, INF);
vector<int> pre(n, -1);
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : to[v]) {
if (dist[u] != INF) continue;
dist[u] = dist[v] + 1;
pre[u] = v;
q.push(u);
}
}
cout << "Yes\n";
rep(i, n) {
if (i == 0) continue;
int ans = pre[i];
++ans;
cout << ans << '\n';
}
return 0;
}
正是我想要的!!