题目链接：http://codeforces.com/problemset/problem/1106/D

 

题意：给定一张n个点，m条双向边的图，从1号点出发，沿双向边行走（可以重复经过一个点）。当经过一个之前未经过的点时，记录下其编号。这些编号组成一个长度为n的序列。求字典序最小的序列。

 

思路：

用字典序最小的方法走过图上的所有点，其实就是遍历整张图。因为要满足字典序最小，我们很容易想到Dj算法里面我们用优先队列去维护，使每次都走字典序列最小的。注意本题可以重复走，所以这个算法肯定是正确的

 

 1 #include <iostream>
 2 #include <time.h>
 3 #include <algorithm>
 4 #include <stdio.h>
 5 #include <stdlib.h>
 6 #include <cstring>
 7 #include <map>
 8 #include <queue>
 9 
10 typedef long long LL;
11 
12 using namespace std;
13 const int maxn = 2e5 + 10;
14 
15 struct Edge{
16     int to;
17     int next;
18 }edge[maxn];
19 
20 int cnt = 0;
21 int head[maxn];
22 int vis[maxn];
23 int ans[maxn];
24 priority_queue<int,vector<int>,greater<int> > q;
25 
26 void init(){
27     memset(head,-1, sizeof(head));
28     cnt = 0;
29 }
30 
31 void add(int u,int v){
32     edge[cnt].to = v;
33     edge[cnt].next = head[u];
34     head[u] = cnt++;
35 }
36 
37 int main(){
38     int n,m;
39     scanf("%d%d",&n,&m);
40     init();
41     for (int i=0;i<m;i++){
42         int u,v;
43         scanf("%d%d",&u,&v);
44         add(u,v);
45         add(v,u);
46     }
47     int tot = 0;
48     q.push(1);
49     while (!q.empty()){
50         int now = q.top();
51         q.pop();
52         if (vis[now])
53             continue;
54         vis[now] = 1;
55         ans[tot++] = now;
56         for (int i=head[now];i!=-1;i=edge[i].next){
57             int v = edge[i].to;
58             if (!vis[v]){
59                 q.push(v);
60             }
61         }
62     }
63     for (int i=0;i<tot;i++){
64         printf("%d ",ans[i]);
65     }
66     return 0;
67 }