Đếm số thành phần liên thông của đồ thị trong lập trình, thành phần liên thông

4.4. Các thành phần liên thông mạnh

4.4.1. Phân tích

Thêm vào đồ thị một đỉnh x và nối x với tất cả các đỉnh còn lại của đồ thị bằng các cung định hướng.Khi đó quá trình tìm kiếm theo chiều sâu bắt đầu từ x có thể coi như một quá trình xây dựng cây tìm kiếm theo chiều sâu (cây DFS) gốc x.procedure Visit(u∈V);begin Thêm u vào cây tìm kiếm DFS>; for (∀v: (u, v)∈E) do if v không thuộc cây DFS> then Visit(v);end;begin Thêm vào đồ thị đỉnh x và các cung định hướng (x, v) với mọi v>; Khởi tạo cây tìm kiếm DFS := ∅>; Visit(x);end.Để ý thủ tục thăm đỉnh đệ quy Visit(u). Thủ tục này xét tất cả những đỉnh v nối từ u, nếu v chưa được thăm thì đi theo cung đó thăm v, tức là bổ sung cung (u, v) vào cây tìm kiếm DFS. Nếu v đã thăm thì có ba khả năng xảy ra đối với vị trí của u và v trong cây tìm kiếm DFS:v là tiền bối (ancestor - tổ tiên) của u, tức là v được thăm trước u và thủ tục Visit(u) do dây chuyền đệ quy từ thủ tục Visit(v) gọi tới. Cung (u, v) khi đó được gọi là cung ngược (Back edge).v là hậu duệ (descendant - con cháu) của u, tức là u được thăm trước v, nhưng thủ tục Visit(u) sau khi tiến đệ quy theo một hướng khác đã gọi Visit(v) rồi. Nên khi dây chuyền đệ quy lùi lại về thủ tục Visit(u) sẽ thấy v là đã thăm nên không thăm lại nữa. Cung (u, v) khi đó gọi là cung xuôi (Forward edge).v thuộc một nhánh của cây DFS đã duyệt trước đó, tức là sẽ có một đỉnh w được thăm trước cả u và v. Thủ tục Visit(w) gọi trước sẽ rẽ theo một nhánh nào đó thăm v trước, rồi khi lùi lại, rẽ sang một nhánh khác thăm u. Cung (u, v) khi đó gọi là cung chéo (Cross edge).(Rất tiếc là từ điển thuật ngữ tin học Anh-Việt quá nghèo nàn nên không thể tìm ra những từ tương đương với các thuật ngữ ở trên. Ta có thể hiểu qua các ví dụ).

4.4.2. Cây tìm kiếm DFS và các thành phần liên thông mạnh

Nếu a, b là hai đỉnh thuộc thành phần liên thông mạnh C thì với mọi đường đi từ a tới b cũng như từ b tới a. Tất cả đỉnh trung gian trên đường đi đó đều phải thuộc C.Chứng minhNếu a và b là hai đỉnh thuộc C thì tức là có một đường đi từ a tới b và một đường đi khác từ b tới a. Suy ra với một đỉnh v nằm trên đường đi từ a tới b thì a tới được v, v tới được b, mà b có đường tớia nên v cũng tới được a. Vậy v nằm trong thành phần liên thông mạnh chứa a tức là v∈C. Tương tự với một đỉnh nằm trên đường đi từ b tới a.Định lý 2:Với một thành phần liên thông mạnh C bất kỳ, sẽ tồn tại một đỉnh r ∈C sao cho mọi đỉnh của C đều thuộc nhánh DFS gốc r.

Chứng minh:Trước hết, nhắc lại một thành phần liên thông mạnh là một đồ thị con liên thông mạnh của đồ thị ban đầu thoả mãn tính chất tối đại tức là việc thêm vào thành phần đó một tập hợp đỉnh khác sẽ làm

mất đi tính liên thông mạnh.

Trong số các đỉnh của C, chọn r là đỉnh được thăm đầu tiên theo thuật toán tìm kiếm theo chiều sâu. Ta sẽ chứng minh C nằm trong nhánh DFS gốc r. Thật vậy: với một đỉnh v bất kỳ của C, do C liên thông mạnh nên phải tồn tại một đường đi từ r tới v:(r = x0, x1, ..., xk = v)

Từ định lý 1, tất cả các đỉnh x1, x2, ..., xk đều thuộc C nên chúng sẽ phải thăm sau đỉnh r. Khi thủ tục Visit(r) được gọi thì tất cả các đỉnh x1, x2..., xk=v đều chưa thăm; vì thủ tục Visit(r) sẽ liệt kê tất cả những đỉnh chưa thăm đến được từ r bằng cách xây dựng nhánh gốc r của cây DFS, nên các đỉnh x1, x2, ..., xk = v sẽ thuộc nhánh gốc r của cây DFS. Bởi chọn v là đỉnh bất kỳ trong C nên ta có điều phải chứng minh.Đỉnh r trong chứng minh định lý - đỉnh thăm trước tất cả các đỉnh khác trong C - gọi là chốt của thành phần C. Mỗi thành phần liên thông mạnh có duy nhất một chốt. Xét về vị trí trong cây tìm kiếm DFS, chốt của một thành phần liên thông là đỉnh nằm cao nhất so với các đỉnh khác thuộc thành phần đó, hay nói cách khác: là tiền bối của tất cả các đỉnh thuộc thành phần đó.Định lý 3:

Luôn tìm được đỉnh chốt a thoả mãn: Quá trình tìm kiếm theo chiều sâu bắt đầu từ a không thăm được bất kỳ một chốt nào khác. (Tức là nhánh DFS gốc a không chứa một chốt nào ngoài a) chẳng hạn ta chọn a là chốt được thăm sau cùng trong một dây chuyền đệ quy hoặc chọn a là chốt thăm sau tất cả các chốt khác. Với chốt a như vậy thì các đỉnh thuộc nhánh DFS gốc a chính là thành phần liên thông mạnh chứa a.Chứng minh:Với mọi đỉnh v nằm trong nhánh DFS gốc a, xét b là chốt của thành phần liên thông mạnh chứa v.Ta sẽ chứng minh a ≡ b. Thật vậy, theo định lý 2, v phải nằm trong nhánh DFS gốc b. Vậy v nằm trong cả nhánh DFS gốc a và nhánh DFS gốc b. Giả sử phản chứng rằng a≠b thì sẽ có hai khả năng xảy ra:Khả năng 1: Nhánh DFS gốc a chứa nhánh DFS gốc b, có nghĩa là thủ tục Visit(b) sẽ do thủ tục Visit(a) gọi tới, điều này mâu thuẫn với giả thiết rằng a là chốt mà quá trình tìm kiếm theo chiều sâu bắt đầu từ a không thăm một chốt nào khác.Khả năng 2: Nhánh DFS gốc a nằm trong nhánh DFS gốc b, có nghĩa là a nằm trên một đường đi từ b tới v. Do b và v thuộc cùng một thành phần liên thông mạnh nên theo định lý 1, a cũng phải thuộc

thành phần liên thông mạnh đó. Vậy thì thành phần liên thông mạnh này có hai chốt a và b. Điều này vô lý.Theo định lý 2, ta đã có thành phần liên thông mạnh chứa a nằm trong nhánh DFS gốc a, theo chứng minh trên ta lại có: Mọi đỉnh trong nhánh DFS gốc a nằm trong thành phần liên thông mạnh chứa a. Kết hợp lại được: Nhánh DFS gốc a chính là thành phần liên thông mạnh chứa a.

4.4.3. Thuật toán Tarjan (R.E.Tarjan - 1972)

Chọn u là chốt mà từ đó quá trình tìm kiếm theo chiều sâu không thăm thêm bất kỳ một chốt nào khác, chọn lấy thành phần liên thông mạnh thứ nhất là nhánh DFS gốc u. Sau đó loại bỏ nhánh DFS gốc u ra khỏi cây DFS, lại tìm thấy một đỉnh chốt v khác mà nhánh DFS gốc v không chứa chốt nào khác, lại chọn lấy thành phần liên thông mạnh thứ hai là nhánh DFS gốc v. Tương tự như vậy cho thành phần liên thông mạnh thứ ba, thứ tư, v.v... Có thể hình dung thuật toán Tarjan "bẻ" cây DFS tại vị trí các chốt để được các nhánh rời rạc, mỗi nhánh là một thành phần liên thông mạnh. 

Nhận xét 3:Vấn đề phức tạp gặp phải ở đây là nếu từ một đỉnh v của nhánh DFS gốc r, có một cung chéo đi tới một nhánh khác. Ta sẽ thiết lập giải thuật liệt kê thành phần liên thông mạnh ngay trong thủ tục Visit(u), khi mà đỉnh u đã duyệt xong, tức là khi các đỉnh khác của nhánh DFS gốc u đều đã thăm và quá trình thăm đệ quy lùi lại về Visit(u). Nếu như u là chốt, ta thông báo nhánh DFS gốc u là thành phần liên thông mạnh chứa u và loại ngay các đỉnh thuộc thành phần đó khỏi đồ thị cũng như khỏi cây DFS. Có thể chứng minh được tính đúng đắn của phương pháp này, bởi nếu nhánh Các thuật toán trên đồ thị
DFS gốc u chứa một chốt u" khác thì u" phải duyệt xong trước u và cả nhánh DFS gốc u" đã bị loại bỏ rồi. Hơn nữa còn có thể chứng minh được rằng, khi thuật toán tiến hành như trên thì nếu như từ một đỉnh v của một nhánh DFS gốc r có một cung chéo đi tới một nhánh khác thì r không là chốt.Để chứng tỏ điều này, ta dựa vào tính chất của cây DFS: cung chéo sẽ nối từ một nhánh tới nhánh thăm trước đó, chứ không bao giờ có cung chéo đi tới nhánh thăm sau. Giả sử có cung chéo (v, v") đi từ v ∈ nhánh DFS gốc r tới v" ∉ nhánh DFS gốc r, gọi r" là chốt của thành phần liên thông chứa v".Theo tính chất trên, v" phải thăm trước r, suy ra r" cũng phải thăm trước r. Có hai khả năng xảy ra:Nếu r" thuộc nhánh DFS đã duyệt trước r thì r" sẽ được duyệt xong trước khi thăm r, tức là khi thăm r và cả sau này khi thăm v thì nhánh DFS gốc r" đã bị huỷ, cung chéo (v, v") sẽ không được tính đếnnữa.Nếu r" là tiền bối của r thì ta có r" đến được r, v nằm trong nhánh DFS gốc r nên r đến được v, v đến được v" vì (v, v") là cung, v" lại đến được r" bởi r" là chốt của thành phần liên thông mạnh chứav". Ta thiết lập được chu trình (r"→r→v→v"→r"), suy ra r" và r thuộc cùng một thành phần liên thông mạnh, r" đã là chốt nên r không thể là chốt nữa.Từ ba nhận xét và cách cài đặt chương trình như trong nhận xét 3, Ta có: Đỉnh r là chốt nếu và chỉ nếu không tồn tại cung ngược hoặc cung chéo nối một đỉnh thuộc nhánh DFS gốc r với một đỉnh ngoài nhánh đó, hay nói cách khác: r là chốt nếu và chỉ nếu không tồn tại cung nối từ một đỉnh thuộc nhánh DFS gốc r tới một đỉnh thăm trước r.Dưới đây là một cài đặt hết sức thông minh, chỉ cần sửa đổi một chút thủ tục Visit ở trên là ta có ngay phương pháp này. Nội dung của nó là đánh số thứ tự các đỉnh từ đỉnh được thăm đầu tiên đến đỉnh thăm sau cùng. Định nghĩa Numbering là số thứ tự của đỉnh u theo cách đánh số đó. Ta tính thêm Low là giá trị Numbering nhỏ nhất trong các đỉnh có thể đến được từ một đỉnh v nào đó của nhánh DFS gốc u bằng một cung (với giả thiết rằng u có một cung giả nối với chính u).Cụ thể cách cực tiểu hoá Low như sau:

Trong thủ tục Visit(u), trước hết ta đánh số thứ tự thăm cho đỉnh u và khởi gánLow := Numbering (u có cung tới chính u)Xét tất cả những đỉnh v nối từ u:Nếu v đã thăm thì ta cực tiểu hoá Low theo công thức:Lowmới := min(Lowcũ, Numbering).Nếu v chưa thăm thì ta gọi đệ quy đi thăm v, sau đó cực tiểu hoá Low theo công thức:Lowmới := min(Lowcũ, Low)Dễ dàng chứng minh được tính đúng đắn của công thức tính.Khi duyệt xong một đỉnh u (chuẩn bị thoát khỏi thủ tục Visit(u). Ta so sánh Low và
Numbering. Nếu như Low = Numbering thì u là chốt, bởi không có cung nối từ một đỉnh thuộc nhánh DFS gốc u tới một đỉnh thăm trước u. Khi đó chỉ việc liệt kê các đỉnh thuộc thành phần liên thông mạnh chứa u là nhánh DFS gốc u.Để công việc dễ dàng hơn nữa, ta định nghĩa một danh sách L được tổ chức dưới dạng ngăn xếp và dùng ngăn xếp này để lấy ra các đỉnh thuộc một nhánh nào đó. Khi thăm tới một đỉnh u, ta đẩy ngay đỉnh u đó vào ngăn xếp, thì khi duyệt xong đỉnh u, mọi đỉnh thuộc nhánh DFS gốc u sẽ được đẩy vào ngăn xếp L ngay sau u. Nếu u là chốt, ta chỉ việc lấy các đỉnh ra khỏi ngăn xếp L cho tới khi lấy tới đỉnh u là sẽ được nhánh DFS gốc u cũng chính là thành phần liên thông mạnh chứa u.procedure Visit(u∈V);begin Count := Count + 1; Numbering := Count; {Trước hết đánh số u} Low := Numbering; Đưa u vào cây DFS>; Đẩy u vào ngăn xếp L>; for (∀v: (u, v)∈E) do if v đã thăm> then Low := min(Low, Numbering) else begin Visit(v); Low := min(Low, Low); end; if Numbering = Low then {Nếu u là chốt} begin Thông báo thành phần liên thông mạnh với chốt u gồm có các đỉnh:>; repeat Lấy từ ngăn xếp L ra một đỉnh v>; Output v>; Xoá đỉnh v khỏi đồ thị>; until v = u; end;end;begin Thêm vào đồ thị một đỉnh x và các cung (x, v) với mọi v>; Khởi tạo một biến đếm Count := 0>; Khởi tạo một ngăn xếp L := ∅>; Khởi tạo cây tìm kiếm DFS := ∅>; Visit(x)end.Bởi thuật toán Tarjan chỉ là sửa đổi một chút thuật toán DFS, các thao tác vào/ra ngăn xếp được thực hiện không quá n lần. Vậy nên nếu đồ thị có n đỉnh và m cung thì độ phức tạp tính toán của thuật toán Tarjan vẫn là O(n + m) trong trường hợp biểu diễn đồ thị bằng danh sách kề, là O(n2 ) trong trường hợp biểu diễn bằng ma trận kề và là O(n.m) trong trường hợp biểu diễn bằng danh sách cạnh.Mọi thứ đã sẵn sàng, dưới đây là toàn bộ chương trình. Trong chương trình này, ta sử dụng:• Ma trận kề A để biểu diễn đồ thị.• Mảng Free kiểu Boolean, Free = True nếu u chưa bị liệt kê vào thành phần liên thông nào, tức là u chưa bị loại khỏi đồ thị.• Mảng Numbering và Low với công dụng như trên, quy ước Numbering = 0 nếu đỉnh u chưa được thăm.• Mảng Stack, thủ tục Push, hàm Pop để mô tả cấu trúc ngăn xếp.Input: file văn bản GRAPH.INP:• Dòng đầu: Ghi số đỉnh n (≤ 100) và số cung m của đồ thị cách nhau một dấu cách• m dòng tiếp theo, mỗi dòng ghi hai số nguyên u, v cách nhau một dấu cách thể hiện có cung (u, v) trong đồ thịOutput: file văn bản GRAPH.OUT, liệt kê các thành phần liên thông mạnh

 P_4_04_2.PAS * Thuật toán Tarjan liệt kê các thành phần liên thông mạnhprogram Strong_connectivity;const Input
File = 'GRAPH.INP'; Output
File = 'GRAPH.OUT'; max = 100;var a: array<1..max, 1..max> of Boolean; Free: array<1..max> of Boolean; Numbering, Low, Stack: array<1..max> of Integer; n, Count, Component
Count, Last: Integer; fo: Text;procedure Enter;var i, u, v, m: Integer; fi: Text;begin Assign(fi, Input
File); Reset(fi); Fill
Char(a, Size
Of(a), False); Read
Ln(fi, n, m); for i := 1 to m do begin Read
Ln(fi, u, v); a := True; end; Close(fi);end;procedure Init; {Khởi tạo}begin Fill
Char(Numbering, Size
Of(Numbering), 0); {Mọi đỉnh đều chưa thăm} Fill
Char(Free, Size
Of(Free), True); {Chưa đỉnh nào bị loại} Last := 0; {Ngăn xếp rỗng} Count := 0; {Biến đánh số thứ tự thăm} Component
Count := 0; {Biến đánh số các thành phần liên thông}end;procedure Push(v: Integer); {Đẩy một đỉnh v vào ngăn xếp}begin Inc(Last); Stack := v;end;function Pop: Integer; {Lấy một đỉnh khỏi ngăn xếp, trả về trong kết quả hàm}begin Pop := Stack; Dec(Last);end;function Min(x, y: Integer): Integer;begin if x y then Min := x else Min := y;end;procedure Visit(u: Integer); {Thuật toán tìm kiếm theo chiều sâu bắt đầu từ u}var v: Integer;begin Inc(Count); Numbering := Count; {Trước hết đánh số cho u} Low := Numbering; {Coi u có cung tới u, nên có thể khởi gán Low thế này rồi sau cực tiểu hoá dần} Push(u); {Đẩy u vào ngăn xếp} for v := 1 to n do if Free and a then {Xét những đỉnh v kề u} if Numbering 0 then {Nếu v đã thăm} Low := Min(Low, Numbering) {Cực tiểu hoá Low theo công thức này} else {Nếu v chưa thăm} begin Visit(v); {Tiếp tục tìm kiếm theo chiều sâu bắt đầu từ v} Low := Min(Low, Low); {Rồi cực tiểu hoá Low theo công thức này} end; {Đến đây thì đỉnh u được duyệt xong, tức là các đỉnh thuộc nhánh DFS gốc u đều đã thăm} if Numbering = Low then {Nếu u là chốt} begin {Liệt kê thành phần liên thông mạnh có chốt u} Inc(Component
Count); Write
Ln(fo, 'Component ', Component
Count, ': '); repeat v := Pop; {Lấy dần các đỉnh ra khỏi ngăn xếp} Write(fo, v, ', '); {Liệt kê các đỉnh đó} Free := False; {Rồi loại luôn khỏi đồ thị} until v = u; {Cho tới khi lấy tới đỉnh u} Write
Ln(fo); end;end;procedure Solve;var u: Integer;begin {Thay vì thêm một đỉnh giả x và các cung (x, v) với mọi đỉnh v rồi gọi Visit(x), ta có thể làm thế này cho nhanh} {sau này đỡ phải huỷ bỏ thành phần liên thông gồm mỗi một đỉnh giả đó} for u := 1 to n do if Numbering = 0 then Visit(u);end;begin Enter; Assign(fo, Output
File); Rewrite(fo); Init; Solve; Close(fo);end.

Bài tập

Bài 1

Phương pháp cài đặt như trên có thể nói là rất hay và hiệu quả, đòi hỏi ta phải hiểu rõ bản chất thuật toán, nếu không thì rất dễ nhầm. Trên thực tế, còn có một phương pháp khác dễ hiểu hơn, tuy tính hiệu quả có kém hơn một chút. Hãy viết chương trình mô tả phương pháp sau:Vẫn dùng thuật toán tìm kiếm theo chiều sâu với thủ tục Visit nói ở đầu mục, đánh số lại các đỉnh từ 1 tới n theo thứ tự duyệt xong, sau đó đảo chiều tất cả các cung của đồ thị. Xét lần lượt các đỉnh theo thứ tự từ đỉnh duyệt xong sau cùng tới đỉnh duyệt xong đầu tiên, với mỗi đỉnh đó, ta lại dùng thuật toán tìm kiếm trên đồ thị (BFS hay DFS) liệt kê những đỉnh nào đến được từ đỉnh đang xét, đó chính là một thành phần liên thông mạnh. Lưu ý là khi liệt kê xong thành phần nào, ta loại ngay các đỉnh của thành phần đó khỏi đồ thị.Tính đúng đắn của phương pháp có thể hình dung không mấy khó khăn:Trước hết ta thêm vào đồ thị đỉnh x và các cung (x, v) với mọi v, sau đó gọi Visit(x) để xây dựng cây DFS gốc x. Hiển nhiên x là chốt của thành phần liên thông chỉ gồm mỗi x. Sau đó bỏ đỉnh x khỏi cây DFS, cây sẽ phân rã thành các cây con.Đỉnh r duyệt xong sau cùng chắc chắn là gốc của một cây con (bởi khi duyệt xong nó chắc chắn sẽ lùi về x) suy ra r là chốt. Hơn thế nữa, nếu một đỉnh u nào đó tới được r thì u cũng phải thuộc cây con gốc r. Bởi nếu giả sử phản chứng rằng u thuộc cây con khác thì u phải được thăm trước r (do cây con gốc r được thăm tới sau cùng), có nghĩa là khi Visit(u) thì r chưa thăm. Vậy nên r sẽ thuộc nhánh DFS gốc u, mâu thuẫn với lập luận r là gốc. Từ đó suy ra nếu u tới được r thì r tới được u, tức là khi đảo chiều các cung, nếu r tới được đỉnh nào thì đỉnh đó thuộc thành phần liên thông chốt r.Loại bỏ thành phần liên thông với chốt r khỏi đồ thị. Cây con gốc r lại phân rã thành nhiều cây con.Lập luận tương tự như trên với v" là đỉnh duyệt xong sau cùng (hình dưới).Ví dụ:

DANH SÁCH BÀI VIẾTGiải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search)Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search)Duyệt đồ thị, tìm kiếm đường đi dài nhất, đường đi ngắn nhất trong đồ thị
Kiểm tra tính liên thông của đồ thị trong lập trình
Đồ thị liên thông có nghĩa là từ mọi đỉnh bất kì đều sẽ có đường đi trực tiếp hoặc gián tiếp tới các đỉnh còn lại, ngược lại gọi là đồ thị không liên thông.

Kiểm tra đồ thị liên thông

Mình có 2 đồ thị minh họa sau:

Ví dụ 1: Với đồ thị này là đồ thị liên thông vì tất cả cảnh đỉnh đều tồn tại đường đi trực tiếp hoặc gián tiếp với nhau.

Ta có ma trận cho đồ thị này sẽ là:

4 0 1 0 01 0 1 00 1 0 10 0 1 0Ví dụ 2: Đồ thị này là không liên thông, và nó chia thành 2 đồ thị con liên thông là (1,2) và (3,4).

Ta có ma trận cho đồ thị này sẽ là:

40 1 0 01 0 0 00 0 0 10 0 1 0Vậy ý tưởng làm sao để kiểm tra được đồ thị liên thông, và nếu không liên thông thì sẽ có bao nhiêu đồ thị con liên thông?

Rất đơn giản, xuất phát từ một đỉnh bất kì ta sử dụng giải thuật DFS hoặc BFS để duyệt qua từng đỉnh của đồ thị, đỉnh nào được duyệt qua ta đánh dấu là đã được duyệt. Sau khi chạy hết đoạn chương trình nếu như tất cả các đỉnh đều duyệt qua được tức là đồ thị liên thông, ngược lại nếu sót 1 hoặc nhiều hơn số đỉnh không được duyệt thì đồ thị không liên thông.

Trường hợp đồ thị không liên thông ta muốn đếm số lượng đồ thị con liên thông, sau khi kết thúc đoạn chương trình duyệt ta sẽ tiếp tục xét xem còn đỉnh nào chưa được duyệt thì thực hiện gọi lại hàm duyệt bắt đầu từ đỉnh đó mỗi lần như vậy là một đồ thị con liên thông, thực hiện lặp cho đến khi không còn đỉnh nào.

Vậy ta viết chương trình như sau:

#include #include using namespace std;bool dd<1000>; //Mảng đánh dấu đỉnhint dem=1, dem2=1; //Đếm để đếm số đỉnh, đếm 2 để đếm số đồ thị con liên thông nếu cóvoid BFS(int a<><1000>, int n, int i){dd=1; //Đánh dấu đỉnh được duyệtfor(int j=0;j>n;int a<1000>;cout>a; BFS(a,n,0); //Gọi hàm duyệt đồ thịif(dem==n) cout
Kết quả thực hiện chương trình với 2 ví dụ trên:

Kết quả ví dụ 1

Chương trình cho kết quả là đồ thị liên thông.

Xem thêm: Triệu hựu đình anh có thích nước mỹ không ?' phim: anh có thích nước mỹ không

Kết quả ví dụ 2

Chương trình cho kết quả là đồ thị không liên thông, và đồ thị có 2 đồ thị con liên thông.