Đề bài
Cho đồ thị vô hướng G=<V,E> được biểu diễn dưới dạng danh sách cạnh. Hãy viết chương trình thực hiện duyệt cây theo BFS.
- Dòng đầu tiên chứa 2 số n, m là số đỉnh và số cạnh của đồ thị (1 <= n <= 1000, 1 <= m <= n*(n-1)/2).
- M dòng tiếp theo, mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị (1 <= u, v <= n). Các cạnh được liệt kê theo thứ tự tăng dần của các đỉnh đầu.
Output
- In ra duyệt cây BFS tương ứng
| Input | Output |
110 11 21 2 31 3 41 5 51 10 62 4 73 6 83 7 93 9 106 7 115 8 128 9
|
|
Giải
1#include<bits/stdc++.h>
2#include<iostream>
3using namespace std;
4
5int n, m;
6vector<int> adj[1001];
7bool visited[1001];
8
9void inp() {
10 cin >> n >> m;
11 for(int i = 0; i < m; i++) {
12 int x, y;
13 cin >> x >> y;
14 adj[x].push_back(y);
15
16 // Do thi co huong thi comment dong code sau
17 adj[y].push_back(x);
18 }
19 memset(visited, false, sizeof(visited));
20}
21
22void bfs(int u) {
23 // Khoi tao
24 queue<int> q;
25 q.push(u);
26 visited[u] = true;
27
28 // Lap
29 while(!q.empty()) {
30 int v = q.front(); // Lay phan tu o dau hang doi
31 q.pop(); // xoa bo phan tu o dau ra khoi hang doi
32 cout << v << " ";
33 for(int x: adj[v]) {
34 if(!visited[x]) {
35 q.push(x);
36 visited[x] = true;
37 }
38 }
39 }
40}
41
42int main() {
43 // Chuyen NHAP, XUAT thanh file
44 freopen("lab_3_1_input.INP", "r", stdin);
45 freopen("lab_3_1_output.OUT", "w", stdout);
46
47 // INPUT
48 inp();
49
50 // OUTPUT: duyet DFS
51 bfs(1);
52}