Đề 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 DFS.
- 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 DFS tương ứng
| Input | Output |
19 10 21 2 31 3 41 5 52 4 63 6 73 7 83 9 95 8 106 7 118 9 129 3
|
|
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 dfs(int u) {
23 cout << u << " ";
24 // Danh dau la u da duoc ghe tham
25 visited[u] = true;
26 for(int v: adj[u]) {
27 // Neu dinh v chua duoc tham
28 if(!visited[v]) {
29 dfs(v);
30 }
31 }
32}
33
34int main() {
35 // Chuyen NHAP, XUAT thanh file
36 freopen("lab_2_1_input.INP", "r", stdin);
37 freopen("lab_2_1_output.OUT", "w", stdout);
38
39 // INPUT
40 inp();
41
42 // OUTPUT: duyet DFS
43 dfs(1);
44}