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<=n<=10^5) tổng số thành viên trong cộng đồng BolgenOS. Dòng thứ 2 chứa n số nguyên Fi(1<=Fi<=n) là chỉ số của một người sẽ được gọi điện. • Đầu ra: Dòng đầu tiên là một số nguyên chỉ số lượng tối thiểu cặp (x,y) cần thêm vào. Các dòng tiếp theo in ra các cặp (x,y) tương ứng. • Giới hạn thời gian 2s, bộ nhớ 256MB
• 67. Mô hình hóa là một đồ thị G với cung (u,v) là người thứ u sẽ gọi cho người thứ v nếu nhận được tin. Tìm số cạnh nhỏ nhất cần thêm để đồ thị là liên thông mạnh. • Ta thấy nỗi đỉnh trong đồ thị có bán bậc ra đúng bằng 1 do một người khi nhận được tin chỉ gọi cho một người khác.
• 68. Đầu tiên, xét các đỉnh u có bán bậc vào bằng 0, duyệt đường đi bắt đầu tại u, đánh dấu u là đỉnh bắt đầu. Duyệt đến khi gặp đỉnh đã duyệt qua rồi, tức là đến khi gặp cạnh ngược , đánh dấu điểm đó là điểm kết thúc của đường đi. • Tiến hành duyệt những đỉnh w chưa được đi qua trong đồ thị G tại bước 1. Những đỉnh này thuộc vào các thành phần liên thông khác nhau trong G. Điểm bắt đầu và kết thúc của đường đi này đều là w. Đánh dấu các điểm thuộc thành phần liên thông bắt đầu tại w là đã duyệt. • Nối các đường đi lại với nhau bằng cách thêm các cung từ đỉnh kết thúc thành phần thứ i sang đỉnh bắt đầu thành phần thứ (i+1)%k với k là số đường đi của đồ thị G. Nếu k=1,và đỉnh đầu trùng đỉnh cuối G có duy nhất một đường đi, do đó G là đồ thị liên thông mạnh, không cần thêm bất của cung nào nữa. Với k>=2 cần thêm k cạnh để nối k thành phần lại với nhau.
• 69. Với bộ dữ liệu đầu vào 3 3 3 2 • Đồ thị tương ứng • Kết quả 3 3 1
• 70. Bộ test • Test 1-9 <100 • 10-20 1000-10000 • 21-30 10000-100000 • 31 đồ thị đã liên thông
• 71. Submit code
• 72. 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
• 73. Đề bài: Có n người bị kẹt trong n phòng khác nhau. Một số phòng bị khóa, một số khác thì không. Điều kiện để mọi người có thể thoát khỏi là tất cả các phòng phải được mở cùng một lúc. Có m công tắc. Mỗi công tắc điều khiển một số phòng, nhưng mỗi phòng chỉ bị điều khiển bởi đúng 2 công tắc. Bạn được đưa trạng thái ban đầu của các phòng. Nhấn bất kỳ công tắc nào nó sẽ đảo ngược trạng thái phòng mà công tắc đó điều khiển. Ví dụ công tắc 1 điều khiển 3 phòng 1, 2, 3 với trạng thái tương ứng là đóng, mở, mở. Khi nhấn công tắc 1 sẽ chuyển thành mở, đóng, đóng.Bạn cần nói cho Sherlock biết liệu có tồn tại một cách nào mở tất cả các phòng tại một thời điểm không.
• 74. Đầu vào: Đòng đầu tiên là 2 số n, m (2<=n<=10^5, 2<=m<=10^5) là số phòng và số công tắc Dòng tiêp theo là n số nguyên ri (ri ⋴{0,1}) là trạng thái các phòng với 0 là phòng bị khóa, 1 là phòng được mở. m dòng tiếp theo là số nguyên xi (0<=xi<=n) và xi số nguyên ngăn cách nhau bởi khoảng trắng chỉ ra các phòng được điều khiển bởi khóa thứ i. Đảm bảo điều kiện phòng trong khoảng từ 1 đến n và mỗi phòng được điều khiển bởi duy nhất 2 công tắc.
• 75. Đầu ra: In ra “YES” nếu có thể mở tất cả các phòng một lúc, ngược lại in ra “NO”. • Giới hạn thời gian 2s, bộ nhớ 256MB
• 76. Chuyển về bài toán đồ thị tô màu các đỉnh. Phòng là các cạnh và công tắc là các đỉnh. Phòng mở ứng với cạnh có giá trị 1, ngược lại nếu đóng thì cạnh có giá trị 0. Nếu phòng có giá trị 1 thì 2 đỉnh nút của nó phải có cùng màu, nếu là 0 thì 2 dỉnh phải có màu khác nhau. Tô màu đỉnh bằng 2 màu, gặp cạnh 0 sẽ đổi màu đỉnh sau đó, nếu gặp cạnh 1 sẽ giữ nguyên màu.
• 77. Bộ dữ liệu đầu vào 3 3 1 0 1 3 1 2 3 1 2 2 1 3 • Đồ thị • Kết quả YES
• 78. Bộ test • 1-9: max 100 phòng, 100 công tắc, mỗi công tắc max 10 phòng • 10-20: 1000 phòng, 1000 công tắc, max 5 phòng • 21-30 1000 phòng, 1000 công tắc, max 100 phòng • 31-40 10000 phòng, 10000 công tắc, max 20 phòng • 41-50 100000 phòng, 100000 công tắc, max 20 phòng • 51 tất cả các phòng đều đóng • 52-55 tất cả các phòng đều mở
• 79. Submit code
• 81.