Bài toán xác định thành phần liên thông năm 2024

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ị.

• 1. LIÊN THÔNG MẠNH VÀ BÀI TOÁN 2-SAT PHÂN TÍCH THIẾT KẾ THUẬT TOÁN GIẢNG VIÊN: TS ĐỖ PHAN THUẬN SINH VIÊN: PHẠM MINH TÂM
• 2. Kosaraju • Thuật toán Tarjan Tìm thành phần liên thông mạnh Bài toán 2-SAT Bài toán 22E - codeforces Bài toán 776D - codeforces
• 3. THÔNG MẠNH • Cho đồ thị có hướng G[V,E]. Đồ thị được gọi là liên thông mạnh nếu tồn tại một đường đi từ u tới v với mọi cặp đỉnh u,v ∈ V. • Một đồ thị con C của G được gọi là một thành phần liên thông mạnh nếu nó liên thông mạnh và tối đại [ nếu thêm bất kỳ đỉnh w ∈ G nào khác vào C thì C không liên thông mạnh nữa. • 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 có chu trình. • Thuật toán tìm thành phần liên thông mạnh: • Kosaraju • Tarjan
• 4. Là một thuật toán tìm thành phần liên thông mạnh trong đồ thị có hướng. • Sử dụng tính chất : trong đồ thị chuyển vị [đồ thị trong đó mọi cung được đảo ngược so với đồ thị ban đầu], các thành phần liên thông mạnh là không đổi so với đồ thị ban đầu.
• 5. đỉnh u chưa thăm : DFS[u] for v với [u,v] ⋴ E && v chưa thăm: DFS[v] Hoàn thành DFS[u], order.push_back[u] Đảo ngược cạnh u= order.pop[]: if u chưa thăm DFS[u] for v với [u,v] ⋴ E && v chưa thăm: DFS[v] Mỗi lần hoàn thành DFS ta được một thành phần liên thông mạnh
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.
• 16.
• 17.
• 18.
• 19.
• 20.
• 21.
• 22.
• 23.
• 24.
• 25.
• 26.
• 27.
• 28.
• 29.
• 30.
• 31. [3,2,1], 2,6,7,5,4,3
• 32. [3,2,1],
• 33. [3,2,1],
• 34. [3,2,1],
• 35. [3,2,1],
• 36. [3,2,1],
• 37. [3,2,1],[5,7,6,4] 2,6,7,5
• 38. Ý tưởng cơ bản của thuật toán này là: tìm kiếm theo chiều sâu bắt đầu từ một đỉnh tùy ý [và sau đó tìm kiếm sâu dần trên bất kỳ các đỉnh nào chưa được xét]. Việc tìm kiếm sẽ không xét đến bất kỳ đỉnh nào đã được xét trước đó. Các thành phần liên thông mạnh tạo nên các cây con của cây tìm kiếm, gốc của những cây con đó chính là gốc của các thành phần liên thông mạnh. • Các đỉnh được đưa vào một ngăn xếp theo thứ tự mà chúng đã được xét. Khi việc tìm kiếm trả về một cây con, các đỉnh được lấy ra khỏi ngăn xếp và được xác định xem liệu mỗi đỉnh được lấy ra có phải là gốc của một thành phần liên thông mạnh hay không. Nếu một đỉnh đã được xác định là gốc của một thành phần liên thông mạnh thì nó và tất cả các đỉnh được lấy ra trước đó hình thành nên thành phần liên thông mạnh.
• 39. đỉnh u chưa thăm : DFS[u]: s.push[u], num[u] = low[u] = count for v với [u,v] ⋴ E && v chưa thăm: DFS[v] low[u] = min[low[u], low[v]] if[low[u] == low[v]] // pop stack cho đến khi nhận được cạnh u
• 40.
• 41.
• 42.
• 43.
• 44.
• 45.
• 46.
• 47.
• 48.
• 49.
• 50.
• 51.
• 52.
• 53.
• 54.
• 55.
• 56.
• 57.
• 58. Kosaraju • Thuật toán Tarjan Tìm thành phần liên thông mạnh Bài toán 2-SAT Bài toán 22E - codeforces Bài toán 776D - codeforces
• 59. Cho m biến logic: a1,a2,…,am và một biểu thức logic C có dạng: C = [u1 ˅ v1]˄ [u2 ˅ v2]˄…˄ [un ˅ vn] Trong đó 𝒖𝒊 và 𝒗𝒊 [𝟏 ≤ 𝒊 ≤ 𝒏] được thay bằng biển logic 𝒂𝒋 hoặc 𝐚𝐣 nào đó. [𝟏 ≤ 𝒋 ≤ 𝒎] Hãy gán giá trị 𝑻𝑹𝑼𝑬/𝑭𝑨𝑳𝑺𝑬 cho các biến 𝒂𝟏, 𝒂𝟐, … , 𝒂𝒎 sao cho biểu thức 𝑪 nhận giá trị 𝑻𝑹𝑼𝑬, hoặc thông báo không thể làm đượcBài toán được đưa về bài toán tìm thành phần liên thông. • Bài toán được đưa về bài toán tìm thành phần liên thông.
• 60. Xây dựng đồ thị có hướng 𝑮 = [𝑽, 𝑬], V = {a1 , a1 , a2 , a2 , … , am , a𝑚} 𝐸 = u → v [ u , v ] ∈ E′ } • Như vậy đồ thị mới sẽ có 2𝑚 đỉnh và 2𝑛 cung có hướng.
• 61. đồ thị 𝑮 = [𝑽, 𝑬], tìm các thành phần liên thông mạnh 𝑪𝟏, 𝑪𝟐, … , 𝑪𝒌. 2. Nếu có hai đỉnh đối lập trong cùng 1 TPLTM thì thông báo bài toán vô nghiệm và kết thúc. 3. Gộp các đỉnh thuộc cùng một TPLTM, xây dựng đồ thị DAG 𝑮𝒄 𝑽𝒄 , 𝑬𝒄 : Vc = { Ci 1 ≤ i ≤ k } Ec = { [Ci → Cj]| ∃u, v ∈ V: u ∈ Ci , v ∈ Cj và [u → v ] ∈ E Ta định nghĩa 2 đỉnh đối lập trên 𝑮𝒄 như sau Ci = Cj ⇔ ∃u ∈ V: u ∈ Ci vàu ∈ C𝑗 4. Trên đồ thị 𝑮𝒄 : 1. Khởi tạo tất cả các đỉnh đều chưa được gán giá trị. 2. Sắp xếp các đỉnh theo thứ tự Topo vào danh sách 𝑳[𝟏 . . 𝒌]. 3. Duyệt các đỉnh lần lượt theo thứ tự “Topo ngược” [𝒖 = 𝑳[𝒌] ⟶ 𝑳[𝟏]]: 1. Nếu đỉnh 𝒖 ∈ 𝑽𝒄 đang duyệt chưa được gán giá trị thì gán 𝒖 = 𝑻𝑹𝑼𝑬. 2. Gán giá trị 𝑭𝑨𝑳𝑺𝑬 cho 𝐮 và ∀𝒗 ∈ 𝑽𝒄 : 𝒗 ∈ 𝑨[𝐮]. 5. Từ cách gán giá trị cho các đỉnh trong 𝑮𝒄 suy ra giá trị của các đỉnh trong 𝑮.
• 62. Với bài toán 2-SAT có 3 biến: [x1˅x2] ˅ [x2˅x3] ˅[x1˅x3] [x1˅x2]: [ x1 x2] và [x2 x1] [x2˅x3]: [x2 x3] và [x3   x2] [x1˅x3]: [x1 x3] và [x3 x1]
• 63. Kết quả : x1: false, x2:true,x3:true
• 64. Kosaraju • Thuật toán Tarjan Tìm thành phần liên thông mạnh Bài toán 2-SAT Bài toán 22E - codeforces Bài toán 776D - codeforces
• 65. Đề bài: Để có thể nhận được tin tức về hệ điều hành mới sớm nhất có thể, cộng đồng BolgenOS từ Nizhni Tagil quyết định phát triển một kế hoạch. Theo kế hoạch đó, thành viên đầu tiên nhận được tin tức sẽ thông báo cho một thành viên khác, thành viên này lại thông báo cho một thành viên khác nữa biết tin tức, cứ như vậy cho đến hết,, vd thành viên thứ i khi nhận được tin tức sẽ thông báo cho thành viên thứ fi. Sau một thời gian, các thành viên nhận thấy kế hoạch của họ không có tác dụng, một số thành viên không nhận được tin tức. Họ muốn bổ sung cho kế hoạch bằng cách thêm vào một số cặp [x,y] với ý nghĩa người thứ x sẽ thồn báo cho cả người thứ y biết về tin tức. Tìm số cặp tối thiểu mà họ phải thêm
• 66. Đầu vào: Dòng đầu tiên là số n [2