1#include<bits/stdc++.h>
2#include<iostream>
3using namespace std;
4
5int n, m; // n: so dinh, m: so canh
6vector<int> adj[1001];
7bool visited[1001];
8int parent[1001];
9
10void inp() {
11 cin >> n >> m;
12 for(int i = 0; i < m; i++) {
13 int x, y;
14 cin >> x >> y;
15 adj[x].push_back(y);
16
17 // Do thi co huong thi comment dong code sau
18 adj[y].push_back(x);
19 }
20
21 // Sap xep cac gia tri trong vector tang dan A-Z
22 for(int i = 1; i <= n; i++) {
23 sort(adj[i].begin(), adj[i].end());
24 }
25
26 memset(visited, false, sizeof(visited));
27}
28
29void dfs(int u) {
30 cout << u << " ";
31 // Danh dau la u da duoc ghe tham
32 visited[u] = true;
33 for(int v: adj[u]) {
34 // Neu dinh v chua duoc tham
35 if(!visited[v]) {
36 dfs(v);
37 }
38 }
39}
40
41void bfs(int u) {
42 // Khoi tao
43 queue<int> q;
44 q.push(u);
45 visited[u] = true;
46
47 // Lap
48 while(!q.empty()) {
49 int v = q.front(); // Lay phan tu o dau hang doi
50 q.pop(); // xoa bo phan tu o dau ra khoi hang doi
51 cout << v << " ";
52 for(int x: adj[v]) {
53 if(!visited[x]) {
54 q.push(x);
55 visited[x] = true;
56 parent[x] = v; // Ghi nhan cha cua x la v
57 }
58 }
59 }
60}
61
62void connected_component() {
63 int cnt = 0; // Khoi tao so thanh phan lien thong ban dau cua do thi = 0
64
65 // Duyet qua cac dinh
66 for(int i = 1; i <= n; i++) {
67 if(!visited[i]) {
68 ++cnt; // Tang so thanh phan lien thong
69 bfs(i);
70 cout << endl;
71 }
72 }
73
74 cout << "Tong so thanh phan lien thong: " << cnt;
75}
76
77int main() {
78 // Chuyen NHAP, XUAT thanh file
79 freopen("lab_4_input.INP", "r", stdin);
80 freopen("lab_4_output.OUT", "w", stdout);
81
82 // INPUT
83 inp();
84
85 // OUTPUT: liet ke cac thanh phan lien thong bang DFS / BFS
86 connected_component();
87}