题目描述

难度分:$1500$

输入$n$，$m(1 \leq n,m \leq 10^5)$和一个无向图的$m$条边。节点编号从$1$开始。

你从$1$出发，沿着边在图上行走，每遇到一个之前没有访问过的点，就把这个点的编号记录下来。你可以重复访问节点。

这个过程直到你记录了$n$个节点编号时停止。

输出这$n$个数的最小字典序。

输入样例$1$

3 2
1 2
1 3

输出样例$1$

1 2 3

输入样例$2$

5 5
1 4
3 4
5 4
3 2
1 5

输出样例$2$

1 4 3 2 5

输入样例$3$

10 10
1 4
6 8
2 5
3 7
9 4
5 6
3 4
8 10
8 9
1 10

输出样例$3$

1 4 3 7 9 8 6 5 2 10 

算法

优先队列的BFS

思想是这样的，当遍历到节点$u$时，需要选一个它直连的编号最小的节点作为下一步的节点。假设这个节点为$v$，那么下一步到$v$之后，因为$u$已经被访问过了，之前$u$节点的所有邻居就可以看做全部越过$u$与$v$直连，并且$u$的所有邻居都不会再经过$u$节点，可以将$u$从它所有邻居节点的邻居列表中删除。这也就是说，$v$的下一步应该是所有与自己连通，且距离最近的节点中，编号最小的那个。但如果将遍历过的节点直接忽略掉，那就成为了与$v$直连的节点中编号最小的那个。

所以我们实现的时候并不要真的去进行节点的搬运，只需要用一个数组$st$标记被访问过的节点即可，从$1$节点开始进行BFS，每次访问队首的节点。由于其最短路的性质，当$u$节点出队时，队列中的所有节点其实都是$u$下一步的候选。而为了得到字典序最小的访问路径，只需要将BFS中的常规改成优先队列即可，一旦堆顶被弹出过$n$次，算法就终止。

复杂度分析

时间复杂度

整个过程其实和堆优化的$Dijkstra$算法是一样的，只是思想不同，因此算法的时间复杂度为$O(mlog_2n)$。

空间复杂度

空间瓶颈就是图的邻接表消耗，因此额外空间复杂度为$O(n+m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>

using namespace std;
const int N = 100010;
int n, m, cnt;
vector<int> graph[N];
bool st[N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
    }
    for(int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    memset(st, 0, sizeof st);
    priority_queue<int, vector<int>, greater<int>> heap;
    heap.push(1);
    st[1] = true;
    cnt = 0;
    while(cnt < n) {
        int cur = heap.top();
        heap.pop();
        cnt++;
        printf("%d ", cur);
        for(int nxt: graph[cur]) {
            if(st[nxt]) continue;
            st[nxt] = true;
            heap.push(nxt);
        }
    }
    return 0;
}