Cho một đồ thị vô hướng G=(V,E). Hãy cho biết số thành phần liên thông của đồ thị và mỗi thành phần liên thông gồm những đỉnh nào.
-Dữ liệu vào từ file lienthong.inp
+ Dòng đầu tiên chứa 2 số n và m là số đỉnh và số cạnh của đồ thị
+ i trong m dòng tiếp theo mỗi dòng chứa 2 số x,y thể hiện có đường đi từ đỉnh x đến đỉnh y
-Kết quả đưa ra file lienthong.out
Dòng đầu tiên chứa số nguyên s là số miền liên thông của đồ thị
i trong số s dòng tiếp theo gồm các đỉnh thuộc miền liên thông
Ví dụ
lienthong.inp
7 7
1 2
2 3
4 5
4 6
4 7
6 6
6 7
lienthong.out
2
1 2 3
4 5 6 7
-
Ý tưởng
-
+ Số liên thông được khởi tạo = 0, các đỉnh ban đầu ở trạng thái chưa xét
+ Duyệt từ đỉnh 1 đến đỉnh n nếu đỉnh i chưa xét thì số liên thông tăng lên 1 và dfs(i)
+ In ra các đỉnh thuộc thuộc 1 miền liên thông
-
Thuật toán
-Solt = 0;
-For(I =1 to n) danhdau[i] = 0 // các đỉnh chưa được xét
-A[i][j] //mảng lưu ma trận kề biểu diễn đồ thị
+) void Liên thông
For(i = 1 to n)
if(danhdau[i] == 0)
{
solt++;
dfs(i);// tìm kiếm theo chiều sâu với đỉnh i
}
+) //tìm kiếm theo chiều sâu tại đỉnh u
void Dfs(int u)
{
danhdau[u] = solt;
for(v =1 to n)
if(A[u][v] == 1 && danhdau[v] == 0) dfs(v);
}
+) Biểu diễn trên màn hình đồ họa: Trình bày flash :
// Nhóm mình còn gặp khó khăn trong việc mô tả thuật toán bằng đồ họa, rất mong được sự giúp đỡ của thầy giáo và các bạn