SỞ GIÁO DỤC VÀ ĐÀO TẠO NAM ĐỊNH
TRƯỜNG THPT CHUYÊN LÊ HỒNG PHONG
(TÊN CƠ QUAN, ĐƠN VỊ CHỦ QUẢN)
(TÊN CƠ QUAN ÁP DỤNG SÁNG KIẾN)
BÁO CÁO SÁNG KIẾN
BÁO CÁO
SÁNG KIẾN
(Tên sáng kiến)
PHÁT TRIỂN TƯ DUY CỦA HỌC SINH
THÔNG QUA VIỆC TỐI ƯU HĨA
Tác giả:...................................................................
CÁCTrình
BÀI
TỐN
TRÊN ĐỒ THỊ
độ chun
mơn:...........................................
ChứcTin
vụ:.................................................................
Lĩnh vực:
(14)/THPT
NơiĐặng
cơng tác:...................................................................
Tác giả:
Trung Kiên
Trình độ chun mơn: Cử nhân
Chức vụ: Giáo viên
Nơi cơng tác: Trường THPT chuyên Lê Hồng Phong
THÔNG TIN CHUNG VỀ SÁNG KIẾN
1. Tên sáng kiến: Vận dụng stack, queue trong việc bồi dưỡng học sinh giỏi
2. Lĩnh vực áp dụng sáng kiến: Tin học
3. Thời gian áp dụng sáng kiến:
Từ ngày 06 tháng 09 năm 2018 đến ngày 1 tháng 05 năm 2019
4. Tác giả:
Họ và tên: Đặng Trung Kiên
Năm sinh: 1990
Nơi thường
trú: Định,
11/49 đường
Văn Can,
Thành2021
phố Nam Định
Nam
ngày Lương
20 tháng
04 năm
Trình độ chun mơn: Cử nhân Sư phạm Tin học
Chức vụ công tác: Giáo viên
1
THÔNG TIN CHUNG VỀ SÁNG KIẾN
1. Tên sáng kiến: Phát triển tư duy học sinh thông qua việc tối ưu hóa các
bài tốn trên đồ thị
2. Lĩnh vực: Tin học (14)/THPT
3. Thời gian áp dụng sáng kiến: Từ ngày 06 tháng 09 năm 2021 đến ngày
22 tháng 05 năm 2022
4. Tác giả:
Họ và tên: Đặng Trung Kiên
Năm sinh: 1990
Nơi thường trù: 2D/13/71 đường Phù Nghĩa, Phường Hạ Long, thành phố
Nam Định
Trình độ chun mơn: Cử nhân Sư phạm Tin học
Chức vụ công tác: Giáo viên Tin học
Nơi làm viêc: Trường THPT chuyên Lê Hồng Phong
Điện thoại: 0389905703
Tỷ lệ đóng góp tạo ra sáng kiến: 100%
5. Đồng tác giả: không
6. Đơn vị áp dụng sáng kiến:
Tên đơn vị: Trường THPT chuyên Lê Hồng Phong
Địa chỉ: 76 Vị Xuyên, P. Vị Xuyên, TP Nam Định
2
BÁO CÁO SÁNG KIẾN
Điều kiện hoàn cảnh tạo ra sáng kiến
I.
Lý thuyết đồ thị có rất nhiều thuật tốn ứng dụng vào các bài toán thực tế của cuộc sống
như tìm đường đi ngắn nhất, tìm cây khung có trọng số nhỏ nhất,…Việc tìm ra mối liên hệ giữa
các bài toán thực tế trong cuộc sống với các thuật toán trên đồ thị, khiến cho học sinh cảm thấy
hứng thú rất lớn với lý thuyết về đồ thị. Tuy nhiên, có một khó khăn khi dạy học về lý thuyết đồ
thị, đó là số lượng thuật tốn liên quan đến đồ thị không hề nhỏ. Do vậy, học sinh khi làm các bài
tập liên quan đến đồ thị, các em thường có nhiều thuật tốn khác nhau để giải quyết vấn đề. Đôi
khi, các em cảm thấy chưa biết phải vận dụng thuật toán nào để giải quyết các bài toán trên đồ thị.
Việc dạy cho các em nhiều thuật toán trên đồ thị trong một thời gian ngắn, khiến cho các em cảm
thấy đồ thị thật là khó. Do đó, tơi muốn tiếp cận cách giải quyết những bài toán trên đồ thị, dựa
trên việc phát triển từ những thuật toán, phương pháp cơ bản các em cảm thấy quen thuộc như số
học, quy hoạch động, tổ hợp,…
Vì thế tôi chọn đề tài: “Phát triển tư duy học sinh thơng qua việc tối ưu hóa các
bài tốn trên đồ thị”, nhằm mục đích xây dựng một hệ thống bài tập liên quan đến đồ thị,
đồng thời rèn luyện kỹ năng tối ưu hóa bài tốn trên đồ thị
II. Mơ tả giải pháp
1. Mô tả giải pháp trước khi tạo ra sáng kiến
Trước khi dạy bài tập về đồ thị, phương pháp dạy học của tơi được tiến hành
như sau:
• Tơi thường tìm kiếm bài tập về đồ thị với nguồn từ sách giáo khoa, sách bài
tập, các nguồn bài tập trên Internet, và các sách tham khảo
Tuy nhiên, sau thời gian dạy cho đội tuyển Tin, tôi nhận thấy các vấn đề sau:
• Một là, bài tập tơi xây dựng vẫn chưa đi theo mạch logic từ dễ đến khó.
Khiến cho một số đơn vị bài tập quá dễ, một số đơn vị bài tập lại quá khó.
Điều đó khiến cho bài dễ thì học sinh nảy sinh tâm lý chủ quan, bài khó q
thì nhiều học sinh sẽ nảy sinh tâm lý sợ sệt và nản khi học lập trình
3
• Hai là, cần thiết phải có một hệ thống bài tập khơng q dễ cũng khơng q
khó, và nằm trong khả năng có thể làm được của nhiều đối tượng học sinh.
Hệ thống bài tập như vậy sẽ khiến cho học sinh cảm thấy thích thú tìm hiểu
lập trình, và khai thác sâu được nhiều đơn vị kiến thức qua mỗi bài tốn
trong Tin học
Do vậy, tơi viết chun đề này với mục đích sau:
• Xây dựng được một hệ thống bài tập có vận dụng đồ thị trong việc tối ưu
hóa thuật tốn; chỉ ra được thuật tốn tối ưu và thuật toán chưa tối ưu trong
việc giải quyết bài tốn, và cài đặt chương trình bằng ngơn ngữ lập trình
C++
2. Mơ tả giải pháp sau khi có sáng kiến
Đề tài tơi xây dựng hướng tới mục đích sau:
• Xây dựng và phân tích được những bài tập đồ thị có nhiều cách giải, sử dụng những
thuật tốn cơ bản trên đồ thị như dfs, bfs, tìm đường đi ngắn nhất,…. sau đó tối ưu
hóa chúng bằng các phương pháp cơ bản của lớp 10 như số học, quy hoạch động, tổ
hợp,…
• Hệ thống hóa các bài tập cơ bản trên đồ thị, nhằm giúp cho việc phát triển tư duy của
học sinh theo mạch logic.
• Rút ra được kinh nghiệm cài đặt các bài tập liên quan đến đồ thị
• Hình thành kỹ năng tối ưu hóa các bài toán về đồ thị
Nội dung sáng kiến kinh nghiệm của tơi gồm có 2 phần: Phần I là Lý thuyết, nêu
một số lý thuyết học sinh cần nắm vững trước khi bắt đầu với các bài toán trên đồ
thị. Phần 2 là bài tập vận dụng:
I.
Một số khái niệm cơ bản
1. Ma trận kề
4
Trong lý thuyết đồ thị, một ma trận kề là một ma trận được sử dụng để biểu
diễn đồ thị. Các phần tử của ma trận biểu thị liệu có cạnh nối giữa hai đỉnh trong
đồ thị hay khơng. Hình minh họa dưới đây mô phỏng cách biểu diễn một đồ thị
bằng ma trận kề:
Đồ thị
Ma trận kề biểu diễn đồ thị
0
0
0
0
0
1
2
5
3
4
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
Ma trận trên gồm có 5 hàng, 5 cột,
phần tử có giá trị 1 biểu thị có cạnh
nối giữa 1 và 2, 2 và 3, 4 và 5, phần
tử có giá trị 0 biểu thị khơng có
cạnh nối giữa chúng
2. Danh sách kề
Một danh sách kề là một mảng các danh sách, nghĩa là, mỗi phần tử của
mảng ai là một danh sách, danh sách đó chứa tất cả các đỉnh liền kề với đỉnh i
Với đồ thị có trọng số, trọng số của cạnh được lưu cùng với đỉnh trong
danh sách bằng cách sử dụng cấu trúc pair trong C++.
Với đồ thị vô hướng, nếu đỉnh j trong danh sách của ai, thì đỉnh i cũng sẽ
được lưu trong danh sách của aj
Chúng ta cùng nhau quan sát đồ thị sau:
1
2
4
3
Đỉnh số 1 được nối với đỉnh số 2 và đỉnh số 4, ta sẽ biểu diễn:1->2->4
Đỉnh số 2 được nối với đỉnh số 1 và 3, ta sẽ biểu diễn: 2->1->3
Đỉnh số 3 được nối với đỉnh số 2 và 4, ta sẽ biểu diễn: 3->2->4
Đỉnh số 4 được nối với đỉnh số 1 và 3, ta sẽ biểu diễn 4->1->3
Ta xét đồ thị có hướng sau đây:
5
1
2
3
4
Đỉnh số 1 được nối với đỉnh số 2, ta sẽ biểu diễn: 1->2
Đỉnh số 2 được nối với đỉnh số 4, ta sẽ biểu diễn: 2->4
Đỉnh 3 nối với đỉnh số 1 và 4, ta sẽ biểu diễn: 3->1->4
Đỉnh số 4 được nối với đỉnh số 2, ta sẽ biểu diễn: 4->2
Ví dụ sau đây biểu diễn một đồ thị vơ hướng gồm có N đỉnh và M cạnh
(trong đó 1<=n<=105, 1<=m<=n*(n-1)/2). Input của dịng đầu tiên là số đỉnh,
dòng thứ hai là số cạnh, m dòng tiếp theo mỗi dịng gồm hai đỉnh a và b, mơ tả
cạnh nối giữa đỉnh a và đỉnh b. Output: Đưa ra danh sách kề của các đỉnh
Danhsachke.inp
Danhsachke.out
4
Danh sach ke cua nut 1: 2
5
Danh sach ke cua nut 2: 4
12
Danh sach ke cua nut 3: 1 --> 4
24
Danh sach ke cua nut 4: 2
31
34
42
#include<bits/stdc++.h>
using namespace std;
vector <int> adj[10];
int main()
{int x, y, nodes, edges;
freopen("danhsachke.inp","r",stdin);
freopen("danhsachke.out","w",stdout);
cin >> nodes;
//So nut
cin >> edges;
//So canh
for(int i = 0;i < edges;++i)
{
cin >> x >> y;
adj[x].push_back(y);
//Chen nut y vao danh sach ke cua x
}
for(int i = 1;i <= nodes;++i)
6
{
cout << "Danh sach ke cua nut " << i << ": ";
for(int j = 0;j < adj[i].size();++j)
{
if(j == adj[i].size() - 1)
cout << adj[i][j] << endl;
else
cout << adj[i][j] << " --> ";
}
}
return 0;
}
Độ phức tạp về mặt không gian của danh sách kề là O(V+E), phụ thuộc vào
số đỉnh và số cạnh. Trong nhiều trường hợp, một ma trận kề khơng thực sự hữu
ích bằng danh sách kề. Bởi vì sử dụng ma trận liền kề sẽ mất nhiều không gian bộ
nhớ để lưu các phần tử là số 0.
3. Thuật tốn tìm kiếm đồ thị theo chiều rộng (BFS)
Trong lý thuyết đồ thị, tìm kiếm theo chiều rộng (BFS) là một thuật tốn tìm
kiếm trong đồ thị trong đó việc tìm kiếm chỉ bao gồm 2 thao tác: (a) cho trước
một đỉnh của đồ thị; (b) thêm các đỉnh kề với đỉnh vừa cho vào danh sách có thể
hướng tới tiếp theo. Có thể sử dụng thuật tốn tìm kiếm theo chiều rộng cho hai
mục đích: tìm kiếm đường đi từ một đỉnh gốc cho trước tới một đỉnh đích, và
tìm kiếm đường đi từ đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị khơng có
trọng số, thuật tốn tìm kiếm theo chiều rộng ln tìm ra đường đi ngắn nhất có
thể. Thuật tốn BFS bắt đầu từ đỉnh gốc và lần lượt nhìn các đỉnh kề với đỉnh
gốc. Sau đó, với mỗi đỉnh trong số đó, thuật tốn lại lần lượt nhìn trước các đỉnh
kề với nó mà chưa được quan sát trước đó và lặp lại. Cấu trúc dữ liệu được sử
dụng là hàng đợi (queue). (Theo Wikipedia)
Hình minh hoạt sau đây mơ phỏng qua trình tìm kiếm đồ thị theo chiều rộng
7
s
1
3
5
8
A
2
4
1
3
5
2
4
C
s
B
s
1
3
5
2
4
D
s
1
3
5
9
2
4
E
s
1
3
5
2
4
F
s
1
3
5
2
4
G
s
1
3
2
4
5
Giải thích: Mũi tên có hướng trong các hình vẽ trên mơ phỏng q trình tìm kiếm
theo chiều rộng, đỉnh được bơi đen nghĩa là đỉnh đó đã được đánh dấu trong quá
trình tìm kiếm. Tại hình C, đỉnh s đã được đánh dấu, vì vậy ta bỏ qua đỉnh s
Tại hình D, đỉnh s và đỉnh số 3 đã được đánh dấu, vì vậy ta bỏ qua
Tại hình E, đỉnh 1 và 2 đã được đánh dấu, vì vậy ta bỏ qua
Tại hình F, đỉnh 2 đã được đánh dấu, vì vậy ta bỏ qua
Tại hình G, đỉnh 3 đã được đánh dấu, vì vậy ta bỏ qua
Mơ phỏng giai đoạn thực hiện của thuật toán:
Thao tác lặp thứ nhất
S sẽ được lấy từ hàng đợi
Đỉnh liền kề của s chính là đỉnh 1 và đỉnh 2 sẽ được duyệt qua
Đỉnh 1 và đỉnh 2, chúng sẽ được đẩy vào hàng đợi, và đỉnh 1 và đỉnh 2 sẽ được
đánh dấu là đã thăm
s
1
2
Thao tác lặp thứ hai
1 sẽ được lấy từ hàng đợi
Đỉnh liền kề của 1 là s và 3 sẽ được duyệt qua
S bỏ qua vì s đã được đánh dấu là đã thăm
3 chưa được đánh dấu, do vậy, sẽ đẩy 3 vào hàng đợi và đánh dấu là đã thăm 3
1
2
3
10
Giai đoạn lặp thứ 3
2 được lấy từ hàng đợi
Đỉnh liền kề của 2 là 3 và 4 được duyệt qua
3 và s bỏ qua vì chúng đã được đánh dấu
4 không được đánh dấu, nên 4 sẽ được đẩy vào hàng đợi
Đánh dấu 4 đã viếng thăm
2
3
4
Giai đoạn 4
3 được lấy từ hàng đợi
Đỉnh liền kề của 3 là 1,2, và 5 được duyệt qua
1 và 2 bỏ qua vì chúng đã được đánh dấu
5 chưa được đánh dấu, vì thế sẽ đẩy 5 vào hàng đợi và đánh dấu 5 đã thăm
3
4
5
Giai đoạn sáu
4 được lấy từ hàng đợi
Đỉnh liền kề của 4 là 2 được duyệt qua
2 bị bỏ qua vì đã được đánh dấu
4
5
Giai đoạn 6
5 được lấy từ hàng đợi
Đỉnh liền kề của 5 là 3 được duyệt qua
3 bỏ qua vì được đánh dấu là đã thăm
Hàng đợi lúc này sẽ trống rỗng và thốt khỏi vịng lặp. Tất cả các đỉnh được duyệt
qua.
Độ phức tạp của thuật tốn BFS là O(V+E) trong đó V là số đỉnh của đồ thị và E
là số cạnh của đồ thị
Ví dụ sau minh họa cách cài đặt đồ thị bằng thuật toán bfs:
Input: File văn bản path.inp. Trong đó: Dịng 1 chứa số đỉnh n(<=100), số cạnh m
của đồ thị, đỉnh xuất phát s, đỉnh kết thúc f cách nhau một dấu cách. M dòng tiếp
theo, mỗi dịng có dạng hai số ngun dương u, v cách nhau một dấu cách, thể
hiện có cạnh nối đỉnh u và đỉnh v trong đồ thị
Ouput file văn bản path.out, danh sách các đỉnh có thể đến được từ s
Path.inp
Path.out
8715
Tu dinh1ban co the toi cac dinh
12
123456
13
Duong di tu 1toi5la
23
5<-3<-1
24
35
46
78
Đây là đoạn chương trình cài đặt có sử dụng queue
11
#include <bits/stdc++.h>
using namespace std;
bool a[101][101]={};
long trace[101]={},n,m,s,f;
void enter()//nhap du lieu
{
long u,v;
//n la so dinh,m la so canh, s la dinh xuat phat
// dinh ket thuc la f
cin>>n>>m>>s>>f;
for(long i=1;i<=m;i++)
{cin>>u>>v;
a[u][v]=a[v][u]=true;
}
}
void bfs()
{ queue<int> ql;
ql.push(s);
//neu hang doi khong rong
while(!ql.empty())
{ //lay gia tri phan tu dau tien trong hang doi
int u=ql.front();
//loai phan tu dau tien ra khoi hang doi
ql.pop();
//tim dinh ke chua di qua lan nao
for(int v=0;v
if(a[u][v]!=0 &&trace[v]==0 )
{ //luu lai nut cha cua dinh v
trace[v]=u;
//them dinh v vao hang doi
ql.push(v);
}
}
}
void result()//in ket qua
{ cout<<"Tu dinh"<
for(long v=1;v<=n;v++)
//in ra nhung dinh den duoc tu s
if (trace[v]!=0) cout<
12
cout<<'\n';
cout<<"Duong di tu "<
if (trace[f]==0) cout<<"khong tim thay";
// khong co duong di tu s toi f
else
{
while (f!=s)
{
cout<
f=trace[f];
}
cout<
}
}
int main()
{ freopen("path.inp","r",stdin);
freopen("path.out","w",stdout);
enter();//nhap du lieu
trace[s]=-1;//ngoai tru s da tham
bfs();
result();//in ket qua
}
4. Thuật tốn tìm kiếm đồ thị theo chiều sâu
Tìm kiếm ưu tiên chiều sâu hay tìm kiếm theo chiều sâu (tiếng Anh: Depth-first
search - DFS) là một thuật tốn duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.
Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển
xa nhất có thể theo mỗi nhánh. Thơng thường, DFS là một dạng tìm kiếm thơng tin
khơng đầy đủ mà quá trình tìm kiếm được phát triển tới đỉnh con đầu tiên của đỉnh
đang tìm kiếm cho tới khi gặp được đỉnh cần tìm hoặc tới một đỉnh khơng có con.
Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước (Theo wikipedia)
Hình minh họa sau đây mơ phỏng q trình tìm kiếm đồ thị của thuật toán
DFS
13
Ví dụ sau minh họa cách cài đặt thuật tốn DFS:
Cho đồ thị vơ hướng gồm có N đỉnh và M cạnh (1<=N<=105, 1<=M<=N*(n1)/2)). Đếm số thành phần liên thông trong đồ thị. Trong lý thuyết đồ thị, một thành
phần liên thông của một đồ thị vô hướng là một đồ thị con trong đó giữa bất kì hai
đỉnh nào đều có đường đi đến nhau, và khơng thể nhận thêm bất kì một đỉnh nào mà
vẫn duy trì tính chất trên. Một đồ thị liên thơng có đúng một thành phần liên thơng,
chính là tồn bộ đồ thị.
14
Hình minh họa đồ thị trên gồm có 3 thành phần liên thơng
Sau đây là phần cài đặt bài tốn ví dụ ở trên bằng cách sử dụng thuật tốn dfs
#include <iostream>
#include <vector>
using namespace std;
vector <int> adj[10];
bool visited[10];
void dfs(int s) {
visited[s] = true;
for(int i = 0;i < adj[s].size();++i)
if(visited[adj[s][i]] == false)
dfs(adj[s][i]);
}
}
void initialize() {
for(int i = 0;i < 10;++i)
15
{
visited[i] = false;
}
int main() {
int nodes, edges, x, y, connectedComponents = 0;
cin >> nodes;
//Number of nodes
cin >> edges;
//Number of edges
for(int i = 0;i < edges;++i) {
cin >> x >> y;
//Undirected Graph
adj[x].push_back(y);
//Edge from vertex x to vertex y
adj[y].push_back(x);
//Edge from vertex y to vertex x
}
initialize();
//Initialize all nodes as not visited
for(int i = 1;i <= nodes;++i) {
if(visited[i] == false) {
dfs(i);
connectedComponents++;
}
}
cout << "Number of connected components: " << connectedComponents <<
endl;
return 0;
}
II.
. Độ phức tạp khơng gian của DFS thấp hơn của BFS (tìm kiếm theo chiều rộng).
Độ phức tạp thời gian của hai thuật toán là tương đương nhau và bằng O(|V| + |E|)
Bài tập vận dụng
Bài tập 1. Cho một đồ thị vô hướng bao gồm N đỉnh và M cạnh. Đồ thị có thể bao
gồm việc nối từ một đỉnh tới chính nó. Cho Q truy vấn, với mỗi truy vấn, cho 2 số
nguyên A và B, bạn cần phải đưa ra câu trả lời xem có đỉnh nối giữa A và B hay
khơng. Nếu có, đưa ra câu trả lời YES. Nếu khơng, đưa ra câu trả lời là NO
Input: Dịng đầu tiên gồm hai số nguyên N và M biểu thị số đỉnh và số cạnh tương
ứng
Mỗi dòng trong M cạnh tiếp theo gồm 2 số nguyên A và B biểu thị một cạnh vô
hướng giữa đỉnh A và B. Dòng tiếp theo gồm số nguyên Q biểu thị số truy vấn.
Dòng tiếp theo gồm 2 số nguyên A và B biểu thị chi tiết truy vấn
Output
Đưa ra Q dòng, câu trả lời cho mỗi truy vấn trên một dòng
16
Giới hạn
1<=N<=103
1<=M<=103
1<=A,B<=N
1<=Q<=103
Phân tích bài tốn: Độ phức tạp về mặt không gian là số đỉnh*số đỉnh =106, cho
nên với bài này ta có thể dùng ma trận kề để cài đặt:
#include <iostream>
using namespace std;
int main()
{
int n,m, a,b, q;
cin>>n>>m;
int adj[n+1][n+1];
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
adj[i][j] = 0;
for(int i=0;i
cin>>a>>b;
adj[a][b] = 1;
adj[b][a] = 1;
}
cin>>q;
for(int i=0;i
cin>>a>>b;
if(adj[a][b] == 1)
cout<<"YES"<< endl;
else
cout<<"NO" << endl;
}
return 0;
}
Bài tập 1 là một ví dụ đơn giản cho việc biểu diễn đồ thị bằng ma trận kề.
Nói chung, ta thường sử dụng ma trận kề khi đồ thị đã cho không quá lớn(<=103),
với đồ thị có số lượng đỉnh và cạnh lớn hơn, ta có thể sử dùng danh sách kề như
bài tập số 2 sau đây
Bài tập 2. Cho đồ thị vơ hướng có N đỉnh, mỗi đỉnh có một giá trị val[i] trong đó
1<=i<=n. Với mỗi đỉnh, có thể có nhiều đỉnh được nối với đỉnh hiện tại. Với mỗi
đỉnh, ta sắp xếp các đỉnh được nối với đỉnh hiện tại theo chiều giảm dần về giá trị
của chúng (trong trường hợp giá trị bằng nhau, thì sắp xếp theo chiều tăng dần về
chỉ số của chúng). Ví dụ, Đỉnh 2 mang giá trị 5 kết nối với đỉnh 1. Đỉnh 3 mang
giá trị 7 kết nối với đỉnh 1
17
Đỉnh 4 mang giá trị 7 kết nối với đỉnh 1. Như vậy đỉnh 3 (sẽ đứng ở vị trí số 1),
sau đó đến đỉnh 4 (đứng ở vị trí số 2), sau đó đến đỉnh 2 (đứng ở vị trí số 3) trong
các đỉnh kết nối với đỉnh 1.
Hãy tìm đỉnh thứ k kết nối với đỉnh hiện tại
Input:
Dịng đầu tiên gồm 3 số nguyên phân biệt là N,M,k biểu thị số đỉnh, số cạnh, và
giá trị k tương ứng. Dịng tiếp theo, có N số ngun phân biệt, val[i], trong đó
1<=i<=N, biểu thị giá trị của đỉnh thứ i. M dòng tiếp theo, mỗi dòng gồm 2 số
nguyên X và Y, biểu thị một cạnh nối giữa X và Y
Ouput: Đưa ra N dịng, trong đó dịng thứ i biểu thị đỉnh ở vị trí thứ k nối với đỉnh
thứ i.
Nếu khơng có đỉnh nào, đưa ra -1
Giới hạn
1<=N<=103
1<=M<=106
1<=k<=M
1
1<=X,Y<=N
Input
Output
332
3
243
1
13
1
12
23
Giải thích: Đỉnh ở vị trí thứ 2 mà nối với đỉnh 1 chính là đỉnh số 3
18
Đỉnh ở vị trí thứ 2 mà nối với đỉnh 2 chính là đỉnh số 1
Đỉnh ở vị trí thứ 2 mà nối với đỉnh 3 chính là đỉnh số 1
Phân tích bài tốn:
Đầu tiên, ta sẽ tạo ra danh sách kề cho mọi đỉnh. Với mỗi đỉnh, ta sẽ có các
đỉnh kết nối trực tiếp với đỉnh hiện tại. Trong danh sách kề, ta sẽ sắp xếp các đỉnh
kết nối trực tiếp với đỉnh hiện tại theo giá trị của chúng
Sau khi tạo danh sách kề, với mỗi đỉnh, ta sẽ sắp xếp các giá trị của các
đỉnh theo thứ tự đảo ngược, sau đó, in đỉnh ở vị trí thứ k trong danh sách với mỗi
đỉnh
Độ phức tạp về mặt thời gian: O(MxlogM)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int ma = 1e5+5;
vector < pair <int, int > > v[1005];
int w[1005];
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>w[i];
int x,y;
for(int i=0;i
{
cin>>x>>y;
v[x].push_back(make_pair(w[y],y));
v[y].push_back(make_pair(w[x],x));
}
for(int i=1;i<=n;i++)
sort(v[i].begin(), v[i].end());
for(int i=1;i<=n;i++)
{
if(v[i].size()>=k)
cout<
else
cout<<"-1"<
}
return 0;
}
19
Như vậy qua bài tập số 1 và bài tập số 2 đã minh họa cách biểu diễn một đồ
thị cơ bản bằng ma trận kề và danh sách kề. Độ phức tạp về mặt không gian khi cài
đặt bằng danh sách kề sẽ nhỏ hơn khi cài đặt bằng ma trận kề.
Bài tập 3. Cho một đồ thị có hình dạng giống như một cây với n nút được đánh số
từ 1 tới n, với 1 cạnh được thêm vào. Cạnh được thêm vào có hai đỉnh khác nhau
được lấy từ các đỉnh 1 đến n, và cạnh này khơng có trong cây trước đó. Trong đó
ai, bi biểu thị cạnh nối giữa ai và bi. Đưa ra cạnh mà sau khi loại bỏ cạnh này, đồ
thị sẽ trở thành một cây gồm có n nút. Nếu có nhiều câu trả lời, hãy đưa ra câu trả
lời xuất hiện ở cuối của input
Giới hạn:
3<=số lượng các đỉnh=số lượng các cạnh<=100000
Ai khác với bi
Khơng có các cạnh lặp lại
Đồ thị đã cho là liên thông
Input
Output
55
14
Minh họa
12
23
34
14
15
Sau khi loại bỏ cạnh 1 4, đồ thị trở thành một
cây
20
33
23
12
13
23
Sau khi loại bỏ một cạnh, đồ thị trở thành
một cây
Cách chưa tối ưu: Ta sẽ làm đúng theo yêu cầu của đề bài, nghĩa là sau khi ta loại
bỏ một cạnh, ta sẽ kiểm tra xem các máy chủ trong mạng có kết nối được với nhau
hay khơng, hay kiểm tra một đồ thị có liên thơng hay khơng. Khi đó, ứng với mỗi
cạnh được loại bỏ, ta sẽ kiểm tra đồ thị đã cho có liên thơng hay khơng bằng cách
sử dụng thuật tốn dfs, hoặc bfs.
Phần cài đặt của thuật toán này như sau:
#include<bits/stdc++.h>
using namespace std;
bool dfs(unordered_map
&m, int node, vector<int> visited, int
parent)
{
if(find(visited.begin(),visited.end(),node)!=visited.end())
return true;
visited.push_back(node);
// cout<for(int v: m[node]){
if(v==parent)
continue;
if(dfs(m,v,visited,node)){
return true;
}
}
21
return false;
}
void findRedundantConnection(vector& A)
{
int n = A.size();
vector<int> visited;
unordered_map m;
for(int i=0;i{
int f = A[i][0];
int s = A[i][1];
m[f].push_back(s);
m[s].push_back(f);
// cout<<"***** "<if(dfs(m,f,visited,-1))
{
cout<}
visited.clear();
}
}
int m,n,a,b;
vector e;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{ vector<int> t;
cin>>a>>b;
t.push_back(a);
t.push_back(b);
e.push_back(t);
}
findRedundantConnection(e);
return 0;
}
Cách tối ưu: Sở dĩ cách trên chưa tối ưu vì lý do ta phải mất cơng tìm lại nhiều
lần mỗi lần xóa bỏ một cạnh. Ta sẽ tìm cách tối ưu bài toán trên bằng cách sử
22
dụng cấu trúc dữ liệu disjointset. Nếu hai đỉnh có cùng cha sẽ kết nối với nhau, ta
có thể loại bỏ cạnh kết nối giữa hai đỉnh này
Sau đây là phần cài đặt của cách tối ưu:
#include<bits/stdc++.h>
using namespace std;
int find(vector<int> &root, int i)
{
//path compression if we don't have the root node
if(root[i] != i)
root[i] = find(root, root[root[i]]);
return root[i];
}
void findRedundantConnection(vector& edges) {
vector<int> root(edges.size() + 1, 0);
//Assign root IDs to root
for(int i = 0; i < root.size(); i++)
root[i] = i;
/*Start iterating through edges.
The idea here is to group the nodes together. Since its connected graph and
only one additional edge is added,
we will come across this additional edge when roots are equal. this will be
our redundant edge.
*/
for(auto vec : edges)
{
int rootA = find(root, vec[0]), rootB = find(root, vec[1]);
if(rootA == rootB)
{
cout<return;
}
root[rootB] = rootA;
}
}
23
int m,n,a,b;
vector e;
int main()
{ // sinhtest();
// freopen("vao.txt","r",stdin);
// freopen("ra.txt","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)
{ vector<int> t;
cin>>a>>b;
t.push_back(a);
t.push_back(b);
e.push_back(t);
}
findRedundantConnection(e);
return 0;
}
Bài tập 4. Chiều cao của một cây
Cho một cây gồm có N đỉnh được đánh số từ 1 tới N và N-1 cạnh. Chiều cao của
một cây là số cạnh trên đường đi dài nhất từ đỉnh gốc tới đỉnh lá của cây. Yêu cầu:
Nếu mỗi đỉnh được coi là một đỉnh gốc, đưa ra chiều cao của cây khi đó.
Input: Dịng đầu tiên gồm số nguyên N (2<=N<=100000). N-1 dòng tiếp theo mỗi
dòng gồm hai số nguyên a và b (1<=a,b<=N) mô tả cạnh vô hướng nối giữa a và b
Giới hạn: 2<=N<=100000
Output: Đưa ra N dòng, dòng thứ i là chiều cao của cây nếu coi đỉnh thứ i là đỉnh
gốc
24
Hình vẽ minh họa:
Chiều cao của cây là một trong những khái niệm cơ bản khi dạy học về cây. Sau khi
dạy xong lý thuyết về cây, giáo viên có thể áp dụng ngay bài tập này để dạy học cho
học sinh
Cách chưa tối ưu:
25
