Song Liên Thông, pà kon Ai biết chỉ dùm

[jelda]

Input: đồ thị vô hướng, n đỉnh, cạnh
biểu diễn dưới dạng danh sách cạnh
VD:
10 15 //10 là số đỉnh, 15 số cạnh
1 2 // 1 kề 2 --> đồ thị có cạnh 1,2
3 4
5 6
...
OutPut: thành phần song liên thông tối đại
song liên thông: 2 đỉnh bất kỳ đều có hai đường đi khác nhau (khác cả cạnh lẫn đỉnh) tới nhau (1 --> 2 khác 2 -->1 )
thành phần song liên thông: các đỉnh trong thành phần này song liên thông zới nhau
VD: output
5 //số thành phần song liên thông
1 2 3 4 //các đỉnh thuộc tp song liên thông 1
5 6 7 //các đỉnh thuộc tp song liên thông 2
...

bài nỳ nhức đầu wá, đành pót lên nhờ mọi người góp ý vậy, ai biết chỉ dùm, giải thuật thui cũng được, code dùm luôn càng tốt
search nát cả google mà chỉ toàn cóc nhái ểnh ương, đọc mấy cuốn sách gòi mà nó cứ lẩn wẩn, chắc bị hư tư duy chỗ nào đó, làm mãi mà cứ tịt

[bete]

google "biconnected":

http://olympiad.cs.uct.ac.za/presentations/camp3_2005/biconnectivity.pdf

www.ecs.umass.edu/ece/labs/vlsicad/ece665/slides/Biconnectivity.ppt

http://users.cs.dal.ca/~nzeh/Teaching/Summer2004/3110/Notes/DFSApps.pdf

http://www.cs.ust.hk/~dekai/271/notes/L06/L06.pdf

http://66.102.7.104/search?q=cache:GYL_anReUfgJ:www.comp.nus.edu.sg/~cs3233/2001/l4.ps+biconnected&hl=en&gl=us&ct=clnk&cd=190

http://www.cs.cmu.edu/afs/andrew.cmu.edu/course/15/354/www/postscript/sccs.pdf

http://www.cs.purdue.edu/homes/ayg/CS251/slides/chap9d.pdf

http://www.cis.nctu.edu.tw/~wuuyang/Lecture.DataStructure/DataStructure06.pdf

http://www.seas.gwu.edu/~ayoussef/cs212/graphsearch.html

-thân

[jelda]

cảm ơn bete
sách thì mình không thíu, Google cũng mòn mặt mình rồi.
chỉ có điều không hỉu giải thuật nó rõ cho lắm (mặt dù sách có, mà vẫn chưa thông lắm, chuối nhỉ), tưởng mọi người bít nên lên hỏi, người bit rồi chỉ sẽ lẹ hơn mà, đỡ tốn thời gian nghiên cứu, dù sao cũng thanks bete, người duy nhất trả lời tui

[bete]

Thân gửi jelda,

Tui xin thử nói theo như những gì tui biết. Giải thuật/code/mã giả thì tui nghĩ bạn đã có rồi, cho nên tui xin khỏi trình bày lại, chỉ xin thử nói về ý chính của thuật toán thôi nghen

Trước hết là về song liên thông (biconnected). Theo định nghĩa thì 2 đỉnh u & v cùng thuộc về 1 thành phần liên thông đôi nếu và chỉ nếu tồn tại ít nhứt 2 đoạn đường (path) không chung đỉnh nối u & v (=> có 1 chu trình chứa cả u lẫn v). Trường hợp đặc biệt: 1 thành phần liên thông đôi chỉ có 2 đỉnh u & v và 1 cạnh duy nhứt nối u và v (không có chu trình nào chứa cả u lẫn v). Có thể nghĩ theo hướng khác: gỡ bỏ 1 đỉnh bất kỳ (và tất cả các cạnh nối với nó) => vẫn còn liên thông. Hai thành phần liên thông đôi bất kỳ nếu có đỉnh chung w thì w thỏa: nếu gỡ bỏ w (và tất cả các cạnh nối với nó) thì đồ thị sẽ không còn liên thông (bằng không thì 2 thành phần liên thông đôi trên đã bị nhập lại làm 1 rồi). Đỉnh w được gọi là đỉnh thắt (xin tạm dịch từ "articulation point"): 1 đỉnh u (khác w) thuộc thành phần liên thông thứ nhứt, 1 đỉnh v (khác w) thuộc thành phần liên thông thứ hai => mọi đoạn đường (path) nối u với v đếu phải đi qua đình w (nếu tồn tại 1 đoạn đường nối u với v mà không qua w thì u & v nằm trên 1 chu trình => cùng thuộc về 1 thành phần liên thông đôi mất rồi)

Kế đến là DFS (depth-first search, duyệt theo chiều sâu): mình để ý DFS đại khái là: giả sử mình đang đứng ở 1 đỉnh bất kỳ u; xét 1 đỉnh bất kỳ v (thỏa: có 1 cạnh e nối u với v), nếu v là chưa đi qua bao giờ thì bước kế là đi tới v theo cạnh e (còn nếu v là đã đi qua rồi thì thôi, kiếm đỉnh khác). Như vậy nếu mình tô đậm các cạnh đã đi qua (như cạnh e ở trên) thì mình sẽ có được 1 cây (DFS tree). Mình để ý: DFS tree là 1 cây nên sẽ không chứa chu trình. Thêm nữa, mình đánh số tăng dần các đỉnh (từ 1 chẳng hạn) theo thứ tự mình duyệt DFS (đỉnh khởi đầu của quá trình DFS là gốc của DFS tree (số thứ tự là 1)).

Cuối cùng, trong quá trình DFS, giả sử mình đang đứng ở đỉnh u. Giả sủ u có các đỉnh con là v1, v2, v3, .... (xét theo DFS tree). Giả sử ở các bước kế tiếp khi mình duyệt DFS 1 đỉnh con vk mà thấy 1 cạnh quay lui (back edge) e thỏa 1 đầu của e là 1 đỉnh con của vk, đầu kia là 1 đỉnh x có số thứ tự nhỏ hơn số thứ tự của v. Khi đó: nếu mình gỡ bỏ đỉnh v (và tất cả các cạnh nối với nó) => đồ thị vẩn còn liên thông (nhờ cạnh quay lui e). Ngược lại, giả sử ở các bước kế tiếp khi mình duyệt DFS 1 đỉnh con vk mà không tìm thấy 1 cạnh quay lui (back edge) e nào thỏa: 1 đầu của e là 1 đỉnh con của vk, đầu kia là 1 đỉnh x có số thứ tự nhỏ hơn số thứ tự của v. Khi đó: nếu mình gỡ bỏ đỉnh v (và tất cả các cạnh nối với nó) => các đỉnh thuộc cây con vk sẽ bị tách rời => u là 1 đỉnh thắt. Để in ra các thành phần liên thông đôi: khi duyệt DFS thì mình bỏ các đỉnh vô 1 stack; khi mình biết u là 1 đỉnh thắt thì mình xóa từ đỉnh stack trở ngược về u và in ra các đình bị xóa

(viết dài, dai, dở, có gì sai sót mong được góp ý, xin cám ơn)

-thân