Bài toán tìm số đỉnh của đồ thị g năm 2024
Xét đơn đồ thị vô hướng G = (V, E) có n(1<=n<=10000) đỉnh và m(1<=m<=50000) cạnh. Người ta định nghĩa một đỉnh gọi là khớp nếu như xoá đỉnh đó sẽ làm tăng số thành phần liên thông của đồ thị. Tương tự như vậy, một cạnh được gọi là cầu nếu xoá cạnh đó sẽ làm tăng số thành phần liên thông của đồ thị. Show Vấn đề đặt ra là cần phải đếm tất cả các khớp và cầu của đồ thị G. Input
OutputGồm một dòng duy nhất ghi hai số, số thứ nhất là số khớp, số thứ hai là số cầu của G Example
TutorialĐây là bài toán tìm cầu khớp cơ bản đầu tiên cần biết. Ý tưởng thuật toán như sau (nên xem thêm Tài liệu chuyên tin quyển 1): Bắt chước ý tưởng từ thuật toán Tarjan, gọi Tạo thêm mảng Ta thực hiện định chiều DFS trong quá trình duyệt dfs tương tự thuật toán Tarjan. Bây giờ vấn đề đặt ra cạnh nào là cầu, đỉnh nào là khớp. Với cầu: Giả sử với cạnh Một vấn đề rất quan trọng trong Lý thuyết đồ thị là bài toán duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó, không duyệt lặp lại cũng như không bỏ sót đỉnh nào cả. Vì vậy, ta phải xây dựng được những phép duyệt các đỉnh của đồ thị theo một hệ thống nhất định, những phép duyệt đó gọi là các thuật toán tìm kiếm trên đồ thị. Có hai giải thuật tìm kiếm trên đồ thị cơ bản: Tìm kiếm theo chiều sâu (Depth First Search - DFS) và Tìm kiếm theo chiều rộng (Breadth First Search - BFS). Hai giải thuật này có độ phức tạp thuật toán như nhau, nhưng sẽ có những ứng dụng khác nhau và cách cài đặt cũng khác nhau. Xét bài toán sau: Cho đơn đồ thị vô hướng gồm nn đỉnh, mm cạnh, danh sách các cạnh được nhập vào theo dạng (u,v)(u, v) với uu và vv là các đỉnh thuộc đồ thị (1≤u≠v≤n)(1 \le u \ne v \le n). Hãy đưa ra một đường đi từ đỉnh ss tới đỉnh ff cho trước. Dưới đây ta sẽ cài đặt hai giải thuật DFS\text{DFS} và BFS\text{BFS} để giải quyết bài toán này. Các cài đặt đều sử dụng danh sách kề, nếu như đề bài thay đổi thành đa đồ thị hay đồ thị có hướng thì chỉ cần sửa đổi một chút trong quá trình nhập dữ liệu. II. Giải thuật tìm kiếm theo chiều sâu (Depth First Search)Tư tưởng thuật toán:
f←p1=parf←p2=parp1←...←sf \leftarrow p_1=par_f \leftarrow p_2=par_{p_1} \leftarrow ... \leftarrow s Cài đặt:
Giả sử với Input là: n=8,m=7,s=1,f=5n = 8, m = 7, s = 1, f = 5 và danh sách các cạnh là {(1,2),(1,3),(2,3),(2,4),(3,5),(4,6),(7,8)}\{(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 6), (7, 8)\}, giải thuật sẽ cho ra kết quả là:
Hình vẽ dưới đây cho ta minh họa về quá trình duyệt DFS\text{DFS}: Nhận xét:
III. Giải thuật tìm kiếm theo chiều rộng (Breadth First Search)Tư tưởng thuật toán:
Thứ tự thăm các đỉnh bằng BFS
Cài đặt:
Nhận xét:
Ví dụ: Giải cứu công chúa: IV. Một số bài toán điển hình của hai giải thuật DFS và BFS1. Đếm thành phần liên thôngĐề bài: Cho đơn đồ thị vô hướng G(V,E)G(V, E) gồm nn đỉnh, mm cạnh (m,n≤105)(m, n \le 10^5). Yêu cầu: Hãy xác định xem đồ thị có bao nhiêu thành phần liên thông? Input:
Output:
Ví dụ: Ý tưởng:
Cài đặt:
2. Tìm đường đi ngắn nhấtĐề bài: Một mê cung được biểu diễn dưới dạng ma trận AA gồm mm hàng, nn cột, các hàng được đánh số từ 11 từ trên xuống, các cột được đánh số từ 11 từ trái sang, ô nằm trên giao của hàng i,i, cột jj có chứa số nguyên ai,ja_{i, j} thể hiện một căn phòng của mê cung. Nếu ai,j=1a_{i, j} = 1 thì phòng đó bị khóa, ngược lại thì phòng đó có thể đi qua. Bạn bị nhốt trong căn phòng ở vị trí (x,y)(x, y) của mê cung, mỗi lần bạn chỉ có thể thử đi vào một trong bốn căn phòng bên trái, bên phải, bên trên và bên dưới. Nếu căn phòng đó bị khóa, bạn không thể đi vào được. Nếu như theo một cách nào đó mà bạn tới được một căn phòng không bị khóa nằm trên biên của mê cung, thì khi đó bạn sẽ thoát khỏi mê cung. Yêu cầu: Tìm số bước đi ngắn nhất để thoát khỏi mê cung (chỉ cần đếm số bước đi để tới được một phòng không khóa bất kỳ trên biên của mê cung)? |