BÀI TOÁN Viết chương trình đếm số thành phần liên thông của đồ thị vô hướng Anxn với: HƯỚNG DẪN THUẬT TOÁN Ý tưởng: Sử dụng thuật toán loang giống như bài toán 2. Bước 0: Khởi tạo số thành phần liên thông bằng 0. Bước 1: Xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thông lên 1 và chuyển sang bước 2. Bước 2: Từ một đỉnh i đã đánh dấu, ta đánh dấu tất cả các đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang bước 3. Bước 3: Thực hiện bước 2 cho đến khi không còn thực hiện được nữa chuyển sang bước 4. Bước 4: Nếu số số đỉnh đánh dấu bằng n (mọi đỉnh đều được đánh dấu) kết thúc thuật toán và trả về số thành phần liên thông, ngược lại quay về bước 1. Chú ý: Nếu số thành phần liên thông bằng 1 đồ thị liên thông. CHƯƠNG TRÌNH MẪU Code:
Như vậy, có thể hiểu một thành phần liên thông mạnh của một đồ thị có hướng là một đồ thị con tối đại liên thông mạnh (nghĩa là nếu thêm vào thành phần liên thông này một tập hợp đỉnh khác sẽ làm mất đi tính liên thông mạnh). Nếu mỗi thành phần liên thông mạnh được co lại thành một đỉnh, thì đồ thị sẽ trở thành một đồ thị có hướng không chu trình. Giải thuật Tarjan là một giải thuật rất được ưa thích để tìm các thành phần liên thông mạnh trên đồ thị. Đồ thị vô hướng ~G(V, E)~ được gọi là liên thông (connected) nếu giữa mọi cặp đỉnh của ~G~ luôn tồn tại đường đi. Ví dụ hình dưới đây là một đồ thị liên thông. Cho đồ thị vô hướng ~G = (V, E)~, ~U~ là một tập con của ~V~. Ta nói ~U~ là một thành phần liên thông của ~G~ nếu hạn chế của ~G~ trên tập ~U: G_U = (U, E_U)~ là một đồ thị liên thông. Ví dụ hình dưới đây là đồ thị có ~3~ thành phần liên thông. Bài toán:Cho đơn đồ thị vô hướng ~G(V, E)~ có ~n~ đỉnh và ~m~ cạnh. Hãy tìm các thành phần liên thông của ~G~. Input
Giới hạn:
Output
Hai số trên cùng một dòng được ghi cách nhau một dấu cách, "các thành phần liên thông liệt kê theo thứ tự các đỉnh nhỏ nhất tăng dần". Xét đồ thị vô hướng, đỉnh khớp (cut vertex) là đỉnh mà nếu xóa đi sẽ làm tăng số thành phần liên thông. Ví dụ trong đồ thị sau, các đỉnh đỏ là đỉnh khớp: Một đồ thị vô hướng được gọi là song liên thông (biconnected) nếu nó liên thông và không có đỉnh khớp, nghĩa là nếu xóa một đỉnh bất kì thì đồ thị vẫn liên thông. Thành phần song liên thôngXét đồ thị vô hướng \(G\), thành phần song liên thông được định nghĩa là đồ thị con song liên thông cực đại của \(G\). Cụ thể hơn, \(G'\) là một thành phần song liên thông của \(G\) thì ta có:
Ví dụ trong hình sau, các đỉnh cùng màu cùng chung một thành phần song liên thông: Ta thấy một đỉnh có thể thuộc vào nhiều thành phần song liên thông khác nhau và các đỉnh thuộc nhiều thành phần song liên thông đều là khớp. Thuật toán tìm thành phần song liên thôngCó nhiều cách để tìm thành phần song liên thông, cách phổ biến nhất là duyệt theo kiểu Tarjan. Tuy nhiên, phần sau sẽ trình bày cách dùng phương pháp nén đường (path compression) và cấu trúc disjoint-sets để tìm thành phần song liên thông. Ý tưởngTa thấy các đỉnh cùng nằm trên một chu trình đơn sẽ cùng thuộc một thành phần song liên thông. Ý tưởng của phương pháp nén đường là kết hợp việc DFS với tìm TP song liên thông, các đỉnh cùng thuộc một TP song liên thông sẽ được hợp nhất lại bằng disjoint-sets. Cụ thể, khi đang duyệt đỉnh \(u\) và có cạnh nối ngược lên \(v\), ta thấy các đỉnh \((v, 2, 3, u)\) tạo nên một thành phần song liên thông, ta sẽ hợp nhất các đỉnh này lại. Mỗi TP sau khi hợp nhất được đại diện bởi đỉnh có bậc nhỏ nhất trên cây DFS. Tuy nhiên, do đỉnh \(v\) có thể thuộc TP song liên thông khác nên ta chỉ hợp nhất từ đỉnh \(2\) đến đỉnh \(u\). Cài đặtTrong quá trình DFS ta sẽ quản lý một stack chứa các đỉnh đang được duyệt, với các đỉnh đã được hợp nhất thì chỉ lưu đỉnh có bậc nhỏ nhất. Ngoài ra ta cũng cần lưu đỉnh con đang được duyệt của mỗi đỉnh. Code như sau:
Sau khi DFS xong, mỗi tập hợp trong disjoint-sets là một TP song liên thông, cộng thêm 1 đỉnh là đỉnh cha của gốc TP song liên thông đó. |