题面：

题目描述：

Bob想在公园散步。公园由n个点和m条无向边组成。当Bob到一个未经过的点时，他就会把这个点的编号记录在笔记本上。当且仅当Bob走完所有的点，他才会停下来。这时，Bob的笔记本记录了一个由n个点编号组成的序列，问：Bob能记录的字典序最小的序列。

 

题目分析：

这道题直观想法就是dfs：

里面还有贪心，最短路等等。

但其实呢，这个很容易被误导，我们还是要认真地分析一下题目：

 

先说一下错误的想法：

每一次dfs选字典序最小的点，比如这样：

但是会有这种情况：

用dfs就会一直往下遍历，输出结果就是：1 2 4 3, 但很明显，这个答案是错的，正确的答案应该是：1 2 3 4。路线：1-2-1-3-1-2-4。

有人说，那么bfs就好了啊。对于这个图来说，确实是这样（bfs遍历顺序：1-2-3-4）。但是对于下面这个图：

很明显，用bfs也是错的（用dfs会输出：1 2 4 3），正确答案：1 2 3 4，路径：1-2-3-2-1-4。

虽然我们尝试了两种方法都不行。但是，从上面的分析我们可以看到：之前走过的点是可以走回去的，只不过走过的点不记录而已。

我们可以根据这点对上面的图进行分析：

刚开始Bob从点1出发，根据字典序最小原则，Bob只能走点2才能使字典序最小：

紧接着，Bob可以在1，2间来回走动，而不改变笔记本的记录结果：

这时，我们发现只要先走：和1，2领接编号最小的点（编号为3）就可以使字典序最小：

往点3走后，Bob可以在1，2，3间来回走动，而不改变笔记本的记录结果：

这时和1，2，3这三个点相连的点只有4，那么往点4走就可以了。最后答案是：1 2 3 4，保证字典序最小。

 

实现：用邻接表（存图），标记数组（维护上图红色区域），优先队列（短时间找到和红色区域相连的编号最小的点）

每当从优先队列取出一个点时，肯定是与红色区域相连的编号最小的点，然后把这个点加入红色区域，再把这个点相连的点加入优先队列就可以了。

 

最后：其实我觉得这个有点像最小生成树prim算法的做法? 

 

AC代码：

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 using namespace std; 8 const int maxn = 1e5+5; 9 int n, m;10 vector
             
               G[maxn]; //vector版邻接表 11 int vis[maxn]; //标记数组 12 13 struct cmp{ //比较函数，优先小的在队列前面 14 bool operator () (int a, int b){15 return a > b;16 }17 };18 19 void solve(){20 priority_queue
              

, cmp> q;21 int u;22 q.push(1);23 24 while(!q.empty()){25 u = q.top(); q.pop();26 27 if(vis[u]) continue; //防止重复访问 28 vis[u] = 1; //标记 29 30 printf("%d ", u); //输出答案 31 32 for(int i = 0; i < G[u].size(); i++){33 q.push(G[u][i]); 34 //把和u相连的点加入优先队列 35 }36 }37 }38 39 int main(){40 scanf("%d%d", &n, &m);41 42 int u, v;43 for(int i = 1; i <= m; i++){44 scanf("%d%d", &u, &v);45 G[u].push_back(v);46 G[v].push_back(u);47 }48 49 solve();50 51 return 0;52 }