SDUT OJ 2141 基于邻接矩阵的BFS

基于邻接矩阵的BFS：
 1  # include <stdio.h>
 2  # include <string.h>
 3  # include <queue>
 4  # include <iostream>
 5  # include <algorithm>
 6  # define N 1010
 7  using namespace std;
 8  
 9  int map[N][N];
10  int vis[N], p[N];
11  queue<int>q;
12  int t = 0, n;
13  
14  void BFS(int s)
15  {
16      vis[s] = 1;
17      for(int i = 0; i < n; i++)
18      {
19          if(!vis[i] && map[s][i])
20          {
21              q.push(i);
22              vis[i] = 1;
23          }
24      }
25      while(!q.empty())
26      {
27          int u = q.front();
28          q.pop();
29          p[t++] = u;
30          BFS(u);
31      }
32  }
33  
34  int main(void)
35  {
36      int m, s, u, v, o;
37      cin >> o;
38      while(o--)
39      {
40          cin >> n >> m >> s;
41          memset(vis, 0, sizeof(v));
42          memset(map, 0, sizeof(map));
43          for(int i = 0; i < m; i++)
44          {
45              cin >> u >> v;
46              map[u][v] = 1;
47              map[v][u] = 1;
48          }
49          q.push(s);
50          BFS(s);
51          for(int i = 0; i < t-1; i++)
52              cout << p[i] << " ";
53          cout << p[t-1] << endl;
54      }
55  
56      return 0;
57  }
58
View Code