Union find là gì
Trong nhiều trường hợp, ta phải quản lý các đỉnh trong đồ thị theo nhiều thành phần rời nhau. Để giải quyết vấn đề này, DSU là một trong những lựa chọn tối ưu. Trong cấu trúc DSU, đại lượng đặc trưng cho mỗi nút là nút cha của nó. Hiển nhiên, nếu nút đang xét là nút gốc của tập không giao (disjoint set) chứa nó thì giá trị đó là chính nó. Có 2 thao tác chính có thể thực hiện trên cấu trúc DSU:
Thông thường, các thao tác này sẽ cần độ phức tạp O(V). Nếu ở thao tác merge, ta thực hiện merge theo phương pháp nhập tập không giao nhỏ hơn vào tập không giao lớn hơn, thì độ phức tạp sẽ chỉ là O(log(V)). Để thực hiện được điều này, ta cần xét thêm một đại lượng nữa, đó là kích thước của mỗi tập không giao. Giá trị này sẽ được truy vấn ở nút gốc của mỗi tập. Tham khảo thêm ví dụ về cách cài đặt (C++) tại đây: Disjoint set union (DSU) Tham khảo thêm ở bài viết về thuật toán Kruskal. Bài toán tham khảo: Codeforces 939D – Love Rescue Tóm tắt đề bài: Cho 2 xâu cùng có độ dài n (1 <= n <= 10^5), chỉ chứa các chữ cái tiếng Anh viết thường. Ta quy ước: cho một tập S, với mỗi cặp ký tự (c1, c2) có trong tập S, ta được quyền đổi bất kỳ ký tự c1 ở bất kỳ xâu nào thành c2, và ngược lại, bất kỳ ký tự c2 nào cũng có thể chuyển thành c1. Hãy tìm kích thước nhỏ nhất của tập S sao cho ta có thể biến 2 xâu trở nên giống nhau hoàn toàn. In ra tập các cặp ký tự đó. Nếu có nhiều đáp án cùng thỏa mãn kích thước S là nhỏ nhất, in ra bất kỳ đáp án nào. Thứ tự các ký tự trong mỗi cặp và thứ tự các cặp là tùy ý. Phương pháp: Ta có thể coi 26 ký tự trong bảng chữ cái tiếng Anh đại diện cho 26 nút của 1 đồ thị vô hướng (có thể không liên thông). Ta nhận thấy: khi xét mỗi một vị trí i (0 <= i < n) trên cả 2 xâu, 2 ký tự tương ứng trên 2 xâu đó phải liên kết với nhau – hay nói cách khác 2 ký tự đó cùng 1 thành phần liên thông. (Nếu 2 ký tự giống nhau thì điều này cũng hiển nhiên đúng). Vậy nên, một trong những cách tìm tập S tối ưu là: đối với 1 thành phần liên thông chứa A ký tự, ta cần vạch ra A-1 đường nối giữa các ký tự trong đó (hay nói cách khác thành phần liên thông được xét sẽ có dạng 1 cây). Nhưng tìm và lưu trữ các nút cùng thuộc 1 thành phần liên thông như thế nào? Với đồ thị chỉ có 26 nút, ta hoàn toàn có thể thực hiện DFS/BFS theo ý tưởng khờ khạo (độ phức tạp O(N^2) thật sự không đáng kể với kích thước đồ thị nhỏ như vậy). Tuy nhiên, mở rộng và tổng quát hóa bài toán, nếu đây không phải là 1 xâu ký tự mà là 1 mảng các số nguyên 64-bit (tối đa có thể trở thành 1 đồ thị chứa 200,000 nút), thì việc dùng DSU sẽ là giải pháp tối ưu nhất. Độ phức tạp sẽ là O(N) (do ta sẽ cần 1 lần duyệt lại toàn bộ các đỉnh để gói chúng vào các thành phần liên thông phù hợp). Lời giải (của D.Bách): Submission 35447195 #ThuyTrang_12A2 DisJoint Set Trong khoa học máy tính, Disjoint Set hay còn gọi là Union-Find hay merge–find set, là một cấu trúc dữ liệu mà theo dõi các phần tử trong các tập con (không chồng lấn). Cấu trúc có hai thao tác chính: 1. Find (Tìm): Xác định tập hợp con chứa phần tử cần tìm. Hàm Find (Tìm) trả về một giá trị là một phần tử của tập hợp, đại diện cho tập hợp ấy; bằng cách so sánh kết quả của hàm Find (Tìm), người ta có thể xác định xem hai phần tử có nằm trong cùng một tập hợp hay không? 2. Union (kết hợp): Hợp các tập con với nhau. Để chính xác hơn, người ta lấy một phần tử cố định đại diện cho một tập. Find(x) trả về giá trị của tập hợp chứa phần tử x và Union (x,y) hợp tập chứa phần tử x với tập chứa phần tử y. Input: Output First Code: Output Second Code: Thuật toán: DisJoinSet - UnionFind - Dsu. // nhatnguyendrgs (c) 2015 - dsu.cpp #include "iostream" #include "stdio.h" #include "string" #include "string.h" #include "algorithm" #include "math.h" #include "vector" #include "set" #include "map" #include "queue" #include "stack" #include "deque" #include "assert.h" using namespace std; typedef vector vi pset(1004); void initSet(int _size) { pset.resize(_size); for (int i = 0; i < _size;i++) pset[i] = i; } int findSet(int i) { return (pset[i] == i) ? i : (pset[i] = findSet(pset[i])); } void unionSet(int i, int j) { pset[findSet(i)] = findSet(j); } bool isSameSet(int i, int j) { return findSet(i) == findSet(j); } int V, E; int main(){ scanf("%d%d", &V, &E); initSet(V); int p, q; for (int i = 0; i scanf("%d%d",&p,&q); unionSet(p, q); } for (int i = 0; i printf("\n"); for (int i = 0; i printf("\n"); return 0; } Second Code (tham khảo Competitive Programming): // nhatnguyendrgs (c) 2015 - dsu.cpp #include "iostream" #include "stdio.h" #include "stdlib.h" #include "string" #include "string.h" #include "algorithm" #include "math.h" #include "vector" #include "map" #include "queue" #include "stack" #include "deque" using namespace std; typedef pair typedef vector typedef vector int n,m; class UnionFind { private: vi p, rank, setSize; int numSets; public: UnionFind(int N) { setSize.assign(N, 1),rank.assign(N, 0),p.assign(N, 0); numSets = N; for (int i = 0; i < N; i++) p[i] = i; } int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i]));} bool isSameSet(int i, int j) { return findSet(i) == findSet(j); } void unionSet(int i, int j) { if (!isSameSet(i, j)) { numSets--; int x = findSet(i), y = findSet(j); if (rank[x] > rank[y]) {p[y] = x; setSize[x] += setSize[y];} else{ p[x] = y; setSize[y] += setSize[x]; if (rank[x] == rank[y]) rank[y]++; } } } int numDisjointSets() { return numSets;} int sizeOfSet(int i) { return setSize[findSet(i)]; } }; int main(){ scanf("%d%d", &n, &m); UnionFind Set(n+4); int u, v; while (m--){ scanf("%d%d", &u, &v); Set.unionSet(u, v); } for (int i = 0; i < n; i++) printf("%d ", i); printf("\n"); for (int i = 0; i < n; i++) printf("%d ",Set.findSet(i)); printf("\n"); return 0; } Input: Output: Code C++
Độ phức tạp:
Hàm root : O(logN)
Hàm merge : O(logN) Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (481.23 KB, 59 trang ) MỤC LỤC Cô lần lượt đọc mã số của từng cặp hai bạn. Hai bạn đó sẽ thuộc cùng nhóm. Dĩ nhiên, nếu bạn A và B cùng nhóm, bạn B và C cùng nhóm thì cả ba bạn A, B và C là cùng nhóm. Cô cũng qui định rằng bạn nào có số hiệu nhỏ nhất trong nhóm sẽ làm nhóm trưởng. Sau m lần ghép cặp như vậy thì các em được chia thành mấy nhóm, hãy liệt kê mã số của các bạn trong từng nhóm. Input: text file Park.inp • Dòng đầu tiên: hai số nguyên dương n và m, • Dòng thứ i trong số m dòng tiếp theo: mỗi dòng hai số nguyên dương a b là mã số của hai bạn được ghép vào cùng nhóm. Output: Hiển thị • Dòng đầu tiên: k − số lượng nhóm • Tiếp đến là k dòng, mỗi dòng liệt kê danh sách một nhóm. Thí dụ Park.inp 8 5 2 5 3 7 8 6 5 1 4 3 Output 3 1 2 5 3 4 7 6 8 Ý nghĩa: Tổng cộng các em được chia thành 3 nhóm. Nhóm thứ nhất gồm 3 bạn có số hiệu là 1, 2 và 5; Nhóm thứ hai 3 bạn: 3, 4 và 7. Nhóm cuối cùng có 2 bạn: 6 và 8. Thuật toán 2 Điều lí thú trong kỹ thuật này là ở điểm nhóm trưởng chính là em mang số hiệu nhỏ nhất trong nhóm. Lúc đầu, chưa ghép cặp thì mỗi em tạo thành một nhóm riêng. Như vậy, lúc đầu ta có n nhóm. Vì mỗi nhóm chỉ có duy nhất 1 em nên chính em đó là nhóm trưởng của chính mình. Ta mường tượng mỗi bạn j phải bám thắt lưng bạn đứng trước i trong cùng nhóm. Theo qui định của cô giáo thì j > i. Riêng nhóm trưởng, do có số hiệu nhỏ nhất nên i tự bám thắt lưng mình. Ta sử dụng mảng nguyên một chiều d[1..n] để quản lí các nhóm. Ta gán d[j] = i nếu bạn j phải bám vào bạn i là bạn có số hiệu nhỏ hơn mình: i j nếu I < j. Lúc đầu ta khởi trị d[i] = i; i = 1..n: i i, với ý nghĩa: lúc đầu mỗi bạn tạo thành một nhóm 1 người và tự mình làm nhóm trưởng, do đó mỗi bạn tự bám thắt lưng mình. Mảng d được gọi là mảng tham chiếu. Như ta sẽ thấy sau này, nhờ d ta có thể nhanh chóng tìm được nhóm trưởng của bất kì em nào. Ta qui ước gọi d là mảng chứa thông tin liên kết giữa các phần tử trong các tập con. d [1] [2] [3] [4] [5] [6] [7] [8] 1 2 3 4 5 6 7 8 Mỗi khi cô giáo yêu cầu ghép cặp (i, j) thì ta hiểu là: nhóm có em i cần hợp (gộp) với nhóm có em j. Để ghép cặp (i, j) ta thực hiện các bước sau đây: Bước 1. Tìm nhóm trưởng x của nhóm có em i; Bước 2. Tìm nhóm trưởng y của nhóm có em j; Bước 3. Quyết định xem ai sẽ là nhóm trưởng của nhóm gộp mới này. Dễ hiểu là nhóm trưởng mới sẽ là em có số hiệu nhỏ nhất trong 2 nhóm trưởng x và y, tức là Min(x,y). Sau đó ta gộp 2 nhóm theo kỹ thuật tham chiếu: Giả sử x < y. Ta chỉ việc gán d[y] = x, yx. Ý nghĩa của việc này là: cô giáo qui định nhóm trưởng y phải bám thắt lưng nhóm trưởng x. Ta suy ra ngay rằng mọi em trong nhóm y đi theo nhóm trưởng y, mà y lại đi theo x nên mọi em trong nhóm y sẽ đi theo x. Nếu x > y ta gán d[x] = y, xy với ý nghĩa tương tự như trên. Nếu x = y thì có nghĩa là i và j hiện ở trong cùng một nhóm (vì có cùng nhóm trưởng) nên ta không phải làm gì. Bạn quan sát lần lượt các hình dưới đây để phát hiện ra qui luật cập nhật từng cặp học sinh theo yêu cầu của cô giáo. d [1] [2] [3] [4] [5] [6] [7] [8] 3 1 2 3 4 2 6 7 8 d [1] [2] [3] [4] [5] [6] [7] [8] 1 2 3 4 2 6 3 8 d [1] [2] [3] [4] [5] [6] [7] [8] 1 2 3 4 2 6 3 6 d [1] [2] [3] [4] [5] [6] [7] [8] 1 1 3 4 2 6 3 6 Để cập nhật cặp (5,1) ta để ý rằng nhóm trưởng của 5 là 2, vì d[5] = 2, nhóm trưởng của 1 là 1, vì d[1] = 1. Vì 1 < 2 nên ta cho nhóm trưởng 2 bám vào nhóm trưởng 1, tức là gán d[2] = 1, 21. 4 d [1] [2] [3] [4] [5] [6] [7] [8] 1 1 3 3 2 6 3 6 Hàm Init khởi trị mảng d[1..n], d[i] = i với ý nghĩa lúc đầu mỗi em tạo thành một nhóm riêng biệt với nhóm trưởng là chính mình. void Initd() { for (int i = 1; i <= n; ++i) d[i] = i; } Để ý rằng x sẽ là nhóm trưởng khi và chỉ khi d[x] = x. Từ đây ta cài đặt ngay được hàm Find(x): xác định nhóm trưởng của nhóm có em x như sau: int Find(int x) { while (x != d[x]) x = d[x]; return x; } Để gộp 2 nhóm: nhóm có em x và nhóm có em y ta lưu ý hai điểm sau đây: • Rất có thể 2 em x và y hiện đã trong cùng một nhóm. Trường hợp này ta không phải làm gì. Hàm sẽ cho ra giá trị 0. Ta thấy x và y cùng nhóm khi và chỉ khi x và y có cùng nhóm trưởng, tức là Find(x) = Find(y). • Nếu 2 em x và y thuộc 2 nhóm khác nhau, Find(x) ≠ Find(y), thì ta thực sự gộp 2 nhóm này và hàm Union cho ra giá trị 1. int Union(int x, int y) { x = Find(x); y = Find(y); if (x == y) return 0; if (x < y) d[y] = x; else d[x] = y; return 1; } Việc cần làm cuối cùng là liệt kê thành viên của mỗi nhóm. Ta duyệt lại mảng d, mỗi khi tìm được một nhóm trưởng i theo hệ thức d[i] = i, do i là nhóm trưởng nên mọi thành viên của nhóm này đều có số hiệu lớn hơn i. Do đặc điểm này nên ta chỉ cần duyệt tiếp mảng d kể từ j = i+1 đến n, nếu nhóm trưởng của j là i thì ta hiển thị thành viên j. Nhớ rằng lúc đầu ta có tổng cộng n nhóm. Mỗi khi ta gộp thực sự 2 nhóm, tức là khi Union(x,y) = 1 thì số lượng nhóm sẽ giảm đi 1. Nhờ nhận xét này ta dễ dàng tính được số nhóm tại thời điểm kết thúc. Kết quả của thuật toán sử dụng kỹ thuật Find-Union không phụ thuộc vào trật tự duyệt các cặp ghép. Độ phức tạp tính toán: Hàm Find thực hiện tối đa n bước tham chiếu x = d[x]. Hàm Union gọi hàm Find do đó có độ phức tạp O(n). Tổng cộng lại, với m cặp ghép ta có độ phức tạp cỡ n.m – tuyến tính theo chiều dài input. Ghi nhớ: Để vận dụng kỹ thuật Find-Union ta cần: 5 1. Khai báo một mảng nguyên d, khởi trị d[i] = i với i = 1..n; 2. Cài đặt hàm Find; 3. Cài đặt hàm Union. Chương trình C++ // Devcpp: park.cpp: Ki thuat Find-Union #include #include #include using namespace std; const int MN const char * int n; // so int m; // so int d[MN]; int soNhom; = 2001; inf = "park.inp"; // input file nguoi cap ghep void Initd() { for (int i = 1; i <= n; ++i) d[i] = i; } int Find(int x) { while (x != d[x]) x = d[x]; return x; } int Union(int x, int y) { x = Find(x); y = Find(y); if (x == y) return 0; if (x < y) d[y] = x; else d[x] = y; return 1; } void Run(){ int i, j, x, y; ifstream f(inf); // mo input file f >> n >> m; // doc so nguoi n, so cap ghep m Initd(); soNhom = n; // luc dau co n nhom for (i = 1; i <= m; ++i){ // duyet cap ghep thu i f >> x >> y; // doc cap ghep x y soNhom -= Union(x,y); // gop nhom co x voi nhom chua y // giam so nhom neu hai nhom khac nhau } f.close(); // dong input file // Giai trinh ket qua cout << "\n So Nhom: " << soNhom; for (i = 1; i <= n; ++i) { if (d[i] == i) { // gap nhom truong cua mot nhom moi cout << "\n Nhom " << i << " "; // Hien thi nhom truong // Hien thi nguoi trong nhom i for (j = i + 1; j <= n; ++j) if (Find(j) == i) cout << j << " "; } } 6 } main() { Run(); cout << endl << "\n\n F I N I ! \n"; return 0; } Chương trình Pascal (* park.pas: Ki thuat Find-Union *) const MN = 2001; nl = #13#10; { xuong dong } inf = 'park.inp'; var n: integer; { so nguoi } m: integer; { so cap ghep } d: array [0..MN] of integer; soNhom: integer; procedure Initd; var i: integer; begin for i := 1 to n do d[i] := i; end; function Find(x: integer): integer; begin while (x <> d[x]) do x := d[x]; Find := x; end; function Union(x, y: integer): integer; begin Union := 0; x := Find(x); y := Find(y); if (x = y) then exit; if (x < y) then d[y] := x else d[x] := y; Union := 1; end; procedure Run; var i,j,x,y: integer; f: text; begin assign(f,inf); reset(f); readln(f,n,m); { doc so nguoi n, so cap ghep m } Initd; // Khoi tri mang d[1..n] = (1..n) soNhom := n; { luc dau co n nhom } for i := 1 to m do begin { duyet cap ghep thu i } readln(f,x,y); // doc cap ghep x y { gop nhom co x voi nhom chua i giam so nhom neu hai nhom khac nhau } soNhom := soNhom - Union(x,y); end; close(f); { dong input file } { Giai trinh ket qua } writeln(nl, ' So Nhom: ', soNhom); for i := 1 to n do 7 begin if (d[i] = i) then begin { gap nhom truong cua mot nhom moi i } write(nl, ' Nhom ',i, ' '); { Hien thi nhom truong } { Hien thi so thanh vien trong nhom i } for j := i+1 to n do if (Find(j) = i) then write(j, ' '); end end end; BEGIN Run; writeln(nl,' F I N I ! '); readln; END. Trong các mục tiếp theo sẽ trình bày các ứng dụng kỹ thuật Find-Union vào các bài toán trên đồ thị. Một đồ thị hữu hạn G = (V, E) bao gồm tập V với n đỉnh mã số từ 1..n và tập cạnh E với các cặp đỉnh (x, y) nối hai đỉnh x và y. Nếu các cạnh (x, y) đều có chiều đi từ đỉnh x đến đỉnh y, xy thì ta có đồ thị có hướng; ngược lại, khi không qui định hướng đi thì ta thu được đồ thị vô hướng. Mỗi cạnh (x, y) của đồ thị vô hướng cho phép ta đi từ đỉnh x đến đỉnh y, xy, hoặc ngược lại, từ đỉnh y đến đỉnh x, xy giống như qui định trong giao thông về đường một hoặc hai chiều. Trong đồ thị có hướng ta dùng thuật ngữ cung (x, y) thay cho cạnh. Trong đơn đồ thị người ta qui định giữa hai đỉnh bất kì x và y có không quá 1 cạnh (cung). Trong sách này, nếu không ghi chú gì thêm, ta ngầm hiểu các đồ thị được cho là đơn đồ thị hữu hạn. 1.2 Thành phần liên thông Cho đồ thị vô hướng G = (V, E) với n đỉnh V = {1, 2, …, n} và m cạnh (x,y) nối đỉnh x với đỉnh y. Hãy tính số thành phần liên thông và liệt kê tập đỉnh trong mỗi thành phần của G. Đây chính là nội dung của bài đi công viên được trình bày qua ngôn ngữ đồ thị. Đồ thị vô hướng G được gọi là liên thông nếu từ một đỉnh bất kì i ta có thể đi theo một số cạnh liền kề nhau của đồ thị để đến một đỉnh j bất kì. Dãy các cạnh liền kề từ đỉnh i đến đỉnh j được gọi là một đường từ i đến j. Với đồ thị vô hướng, khi có đường từ đỉnh i đến đỉnh j thì ta cũng có đường từ đỉnh j đến đỉnh i. Nếu G không liên thông thì G được chia 8 thành các mảnh liên thông, còn gọi là thành phần liên thông, gồm một số đỉnh và cạnh của G. Hãy tưởng tượng mỗi đỉnh của đồ thị như là một hạt cườm, cạnh nối hai đỉnh i và j chính là sợi dây nối hai hạt i và j. Khi đó, G là liên thông khi và chỉ khi ta cầm một hạt bất kì nhấc lên thì tất cả các hạt đều được nhấc theo. Nếu G không liên thông thì mỗi lần nhấc một hạt ta được một mảnh lên thông gồm một số hạt được liên kết với nhau. Ta đặt riêng mảnh đó ra, rồi nhấc một hạt bất kì trong số các hạt còn lại ta sẽ được mảnh liên thông thứ hai,… Nhận xét: G là liên thông khi và chỉ khi số mảnh liên thông của G là 1. Đồ thị trong thí dụ dưới đây gồm 3 mảnh liên thông (1, 5, 2), (4, 3, 7) và (8, 6). Thí dụ graph.inp 8 5 2 5 3 7 8 6 5 1 4 3 Output 3 1 2 5 3 4 7 6 8 Ý nghĩa: Input: Đồ thị có 8 đỉnh và 5 cạnh. Output: Đồ thị có 3 thành phần liên thông. Thuật toán Nhận xét: Số thành phần liên thông của G = số nhóm trưởng. Để tính số thành phần liên thông của G ta thực hiện hai bước sau: Bước 1. Khởi trị d[i] = i; i = 1..n; gán k = n dùng để đếm số mảnh liên thông. Bước 2. Đọc dần từng cạnh (x,y) và thực hiện toán tử k = k – Union(x,y); k sẽ là số thành phần liên thông của G. Lưu ý rằng hàm Union(x,y) cho giá trị 1 nếu thành phần liên thông chứa đỉnh x được gộp thực sự với thành phần liên thông chứa đỉnh y, ngược lại, Union(x,y) = 0 nếu hai đỉnh x và y hiện đang cùng có mặt trong một thành phần liên thông (do đó không cần thiết gộp hai thành phần này). Như vậy ý nghĩa của giá trị ra của hàm Union(x,y) là giảm số lượng thành phần liên thông của G. Dĩ nhiên, sau khi thực hiện hàm Union(x,y) thì hai đỉnh x và y sẽ thuộc cùng một thành phần liên thông. Để cài đặt, ta chỉ cần tách hàm Run trong bài Công viên thành hai hàm. Hàm thứ nhất như đã trình bày ở trên: int SoThanhPhanLienThong(){ int i, x, y, k; ifstream f(inf); // mo input file f >> n >> m; // doc so dinh n va so canh m Initd(); // Khoi tri mang tham chieu d k = n; for (i = 1; i <= m; ++i){ f >> x >> y; // doc 1 canh k -= Union(x, y); // gop 2 thanh phan } f.close(); // dong input file return k; } Hàm thứ hai liệt kê các đỉnh thuộc mỗi thành phần liên thông như sau: Duyệt các đỉnh i trong mảng d, nếu i là nhóm trưởng, tức là Find(i) = i thì duyệt tiếp các đỉnh j = i+1..n và thỏa điều kiện Find(j) = i , tức là j thuộc thành phần liên thông i thì hiển thị đỉnh j. 9 // Liet ke cac thanh phan lien thong void LienThong(){ int i,j; for (i = 1; i <= n; ++i) { if (d[i] == i) { cout << "\n Thanh phan lien thong thuoc dinh " << i << ": "; cout << i << " "; for (j = i + 1; j <= n; ++j) if (Find(j) == i) cout << j << " "; } // end if }// end for } // end LienThong Độ phức tạp: Cỡ n.m với n là số đỉnh, m là số cạnh của G. Chương trình C++ // Devcpp: LienThong.cpp // Dem so thanh phan lien thong cua do thi // vo huong G gom n dinh, m canh #include #include #include using namespace std; const int MN const char * int n; // so int m; // so int d[MN]; = 2001; inf = "graph.inp"; dinh canh void Initd() { for (int i = 1; i <= n; ++i) d[i] = i; } int Find(int x) { while (x != d[x]) x = d[x]; return x; } int Union(int x, int y) { x = Find(x); y = Find(y); if (x == y) return 0; if (x < y) d[y] = x; else d[x] = y; return 1; } int SoThanhPhanLienThong(){ int i, x, y, k; ifstream f(inf); // mo input file f >> n >> m; Initd(); k = n; for (i = 1; i <= m; ++i){ f >> x >> y; // doc 1 canh k -= Union(x, y); // gop 2 thanh phan } f.close(); // dong input file 10 } return k; // Liet ke cac thanh phan lien thong void LienThong(){ int i,j; for (i = 1; i <= n; ++i) { if (d[i] == i) { cout << "\n Thanh phan lien thong thuoc dinh " << i << ": "; cout << i << " "; for (j = i + 1; j <= n; ++j) if (Find(j) == i) cout << j << " "; } // end if }// end for } // end LienThong main() { cout << SoThanhPhanLienThong(); LienThong(); cout << endl << "\n\n F I N I ! \n"; return 0; } Chương trình Pascal (* -----------------------------------LienThg.pas Liet ke cac thanh phan lien thong cua do thi vo huong n dinh, m canh ------------------------------------*) const MN = 2001; nl = #13#10; { xuong dong } inf = 'graph.inp'; var n: integer; { so dinh } m: integer; { so canh } d: array [0..MN] of integer; procedure Initd; var i: integer; begin for i := 1 to n do d[i] := i; end; function Find(x: integer): integer; begin while (x <> d[x]) do x := d[x]; Find := x; end; function Union(x, y: integer): integer; begin Union := 0; x := Find(x); y := Find(y); if (x = y) then exit; if (x < y) then d[y] := x else d[x] := y; Union := 1; 11 end; function SoThanhPhanLienThong: integer; var i,k,x,y: integer; f: text; begin assign(f,inf); reset(f); readln(f,n,m); { doc so dinh n, so canh m } Initd; k := n; { luc dau co n nhom } for i := 1 to m do begin { duyet canh i (x,y) } readln(f,x,y); { gop nhom co x voi nhom chua i giam so nhom neu hai nhom khac nhau } k := k - Union(x,y); end; close(f); { dong input file } SoThanhPhanLienThong := k; end; { Liet ke cac dinh trong moi thanh phan lien thong } procedure LienThong; var i, j: integer; begin for i := 1 to n do if d[i] = i then begin write(nl,' Thanh phan lien thong thuoc dinh ',i, ': ',i); for j := i+1 to n do if Find(j) = i then write(' ',j); end; end; BEGIN writeln(nl, SoThanhPhanLienThong); LienThong; writeln(nl,' F I N I ! '); readln; END. Kết quả 3 Thanh phan liên thong thuoc dinh 1: 1 2 5 Thanh phan liên thong thuoc dinh 3: 3 4 7 Thanh phan liên thong thuoc dinh 6: 6 8 Ghi nhớ Sau khi vận dụng kỹ thuật Find-Union mảng thông tin liên kết d cho ta các thông tin sau đây: Với mỗi đỉnh i = 1..n • d[i] = 1 khi và chỉ khi đỉnh i là "nhóm trưởng", tức là đỉnh đại diện cho một thành phần liên thông trong đồ thị; 12 • Số lượng thành phần liên thông trong G = số lượng nhóm trưởng = số lượng các đỉnh i thỏa điều kiện Find(i) = i; • Hai đinht i và j thuộc cùng một thành phần liên thông khi và chỉ khi Find(i) = Fìd(j); • Mỗi đỉnh i thuộc một thàn phần liên thông duy nhất. 1.3 Tính liên thông Cho đồ thi vô hướng G = (V, E) với n đỉnh V = {1, 2, …, n} và m cạnh (x,y) nối đỉnh x với đỉnh y. Hãy hiển thị 1 nếu đồ thị G liên thông, 0 nếu G không liên thông. Thí dụ graph.inp 8 2 3 8 5 4 5 5 7 6 1 3 Output 0 Ý nghĩa: Input: Đồ thị có 8 đỉnh và 5 cạnh. Output: Đồ thị G không liên thông vì có hơn 1 thành phần liên thông, cụ thể là 3 thành phần: Thuật toán Nhận xét: Đồ thị G liên thông khi và chỉ khi số thành phần liên thông bằng 1. Độ phức tạp: Cỡ n.m với n là số đỉnh, m là số cạnh của G. Chương trình C++ Bạn chỉ cần thêm hàm LienThong() sau đây vào chương trình LienThong.cpp: //cpp int LienThong(){ return (SoThanhPhanLienThong == 1) ? 1 : 0; } Chương trình Pascal Bạn chỉ cần thêm hàm LienThong sau đây vào chương trình LThong.pas: { pas } function LienThong: Boolean; begin LienThong := (SoThanhPhanLienThong = 1); end; Độ phức tạp: Cỡ n.m với n là số đỉnh, m là số cạnh của G. 1.4 Chu trình Cho đồ thi vô hướng G = (V, E) với n đỉnh V = {1, 2, …, n} và m cạnh (x, y) nối đỉnh x với đỉnh y. Hãy hiển thị 1 nếu đồ thị G có chu trình, 0 nếu G không có chu trình. Thí dụ 1 13 graph.inp 8 2 3 8 5 4 5 5 7 6 1 3 Output 0 Ý nghĩa: Input: Đồ thị có 8 đỉnh và 5 cạnh. Output: Đồ thị G không có chu trình. Thí dụ 2 graph.inp 8 2 3 8 5 4 4 3 7 5 7 6 1 3 6 8 Output 1 Ý nghĩa: Input: Đồ thị có 8 đỉnh và 7 cạnh. Output: Đồ thị có chu trình. 3 – 4 – 6 – 8. (đường tô đậm) Thuật toán Nhận xét: Đồ thi G có chu trình khi và chỉ khi trong quá trình ghép cạnh ta gặp một cạnh (x, y) thoả tính chất Union(x, y) = 0. Thật vậy, Union(x, y) = 0 chứng tỏ hai đỉnh x và y thuộc cùng một thành phần liên thông, nghĩa là có đường đi từ y đến x. Nay ta thêm cạnh (x, y) tức là ta có thể đi tiếp thêm một bước nữa từ x đến y, hoặc từ y đến x vì đồ thị là vô hướng. Như vậy là đã xuất hiện một chu trình từ x trở về x. Chú ý rằng thuật toán chỉ cho biết đồ thị có một chu trình nào đó hay không chứ không chỉ ra chu trình cụ thể nào. int ChuTrinh(){ int i, x, y; ifstream f(inf); // mo input file f >> n >> m; // doc so dinh n, so canh m Initd(); for (i = 1; i <= m; ++i){ // duyet cac canh f >> x >> y; // doc canh x y if (Union(x, y) == 0) return 1; // gap chu trinh } f.close(); return 0; // khong chu trinh } Độ phức tạp: Cỡ n.m với n là số đỉnh, m là số cạnh của G. Chương trình C++ // Devcpp: ChuTrinh.cpp // Kiem tra tinh chu trinh // cua do thi vo huong G gom n dinh, m canh #include #include #include 14 using namespace std; const int MN const char * int n; // so int m; // so int d[MN]; = 2001; inf = "graph.inp"; dinh canh void Initd() { for (int i = 1; i <= n; ++i) d[i] = i; } int Find(int x) { while (x != d[x]) x = d[x]; return x; } int Union(int x, int y) { x = Find(x); y = Find(y); if (x == y) return 0; if (x < y) d[y] = x; else d[x] = y; return 1; } int ChuTrinh(){ int i, x, y; ifstream f(inf); // mo input file f >> n >> m; // doc so dinh n, so canh m Initd(); for (i = 1; i <= m; ++i){ // duyet cac canh f >> x >> y; // doc canh x y if (Union(x, y) == 0) return 1; // gap chu trinh } f.close(); return 0; // khong chu trinh } main() { cout << ChuTrinh(); cout << endl << "\n\n F I N I ! \n"; return 0; } Chương trình Pascal (* -----------------------------------ChuTrinh.pas Kiem tra tinh lien thong cua do thi vo huong G gom n dinh, m canh ------------------------------------*) const inf = var n: m: MN = 2001; nl = #13#10; { xuong dong } 'graph.inp'; integer; { so dinh } integer; { so canh } 15 d: array [0..MN] of integer; procedure Initd; var i: integer; begin for i := 1 to n do d[i] := i; end; function Find(x: integer): integer; begin while (x <> d[x]) do x := d[x]; Find := x; end; function Union(x, y: integer): integer; begin Union := 0; x := Find(x); y := Find(y); if (x = y) then exit; if (x < y) then d[y] := x else d[x] := y; Union := 1; end; function ChuTrinh: integer; var i,x,y,GapChuTrinh: integer; f: text; begin assign(f,inf); reset(f); readln(f,n,m); { doc so dinh n, so canh m } Initd; GapChuTrinh := 0; for i := 1 to m do begin { duyet canh thu i: (x,y) } readln(f,x,y); if (Union(x,y) = 0) then begin GapChuTrinh := 1; break; end; end; close(f); { dong input file } ChuTrinh := GapChuTrinh; end; BEGIN writeln(nl, ChuTrinh); writeln(nl,' F I N I ! '); readln; END. 1.5 Cây khung Cây khung (còn gọi là cây bao trùm) của một đồ thị liên thông n đỉnh, m cạnh là cây gồm n đỉnh với số cạnh tối thiểu bảo toàn tính liên thông của đồ thị. Nhận xét: Cây khung của đồ thị n đỉnh, m cạnh có đúng n đỉnh và n−1 cạnh. Thuật toán Kruskal: 16 • Bước 1. Khởi trị với cây khung rỗng; • Bước 2. Duyệt các cạnh: nếu cạnh (u,v) không tạo thành chu trình với cây khung thì nạp (u,v) vào cây khung. Điều kiện để cạnh (u,v) không tạo thành chu trình với cây khung là Union(u, v) = 0. Ta sử dụng mảng khung với mỗi phàn tử là một bản ghi gồm 2 trường nguyên x và y dùng để chứa các cạnh (x,y) được chọn vào cây khung, trong đó x và y là số hiệu hai đỉnh của cạnh. struct canh { int x, y; } khung[MN]; void CayKhung(){ int i, j, u, v, n1; ifstream f(inf); // mo input file f >> n >> m; // doc so dinh n, so canh m Initd(); n1 = n-1; j = 0;// dem so canh cua cay khung for (i = 1; i <= m; ++i){ f >> v >> u; // doc canh (u,v) if (Union(u,v)){ ++j; // nhan canh (u,v) vao cay khung khung[j].x = u; khung[j].y = v; if (j == n1) break; } } f.close(); // dong input file // Giai trinh ket qua cout << "\n Cay Khung gom " << n << " dinh, " << j << " canh:"; for (i = 1; i <= j; ++i) cout << endl << khung[i].x << " " << khung[i].y; } Hoạt động của chương trình được minh họa qua thí dụ sau: graph.inp 8 11 1 2 1 3 1 6 2 4 2 6 3 4 4 5 5 6 5 7 5 8 7 8 Output 1 2 1 3 1 6 2 4 4 5 5 7 5 8 Ý nghĩa: Input: Đồ thị có 8 đỉnh và 11 cạnh. Output: 7 cạnh của cây khung (tô đậm) Chương trình C++ // ST.cpp: Thuat toan Kruskal // Spaning Tree: Tim cay khung // trong do thi lien thong n dinh, m canh #include #include #include using namespace std; const int MN = 2001; const char * inf = "graph.inp"; 17 int n; // so dinh int m; // so canh int d[MN]; struct canh { int x, y; } khung[MN]; void Initd() { for (int i = 1; i <= n; ++i) d[i] = i; } int Find(int x) { while (x != d[x]) x = d[x]; return x; } int Union(int x, int y) { x = Find(x); y = Find(y); if (x == y) return 0; if (x < y) d[y] = x; else d[x] = y; return 1; } void CayKhung(){ int i, j, u, v, n1; ifstream f(inf); // mo input file f >> n >> m; // doc so dinh n, so canh m Initd(); n1 = n-1; j = 0;//n dem so canh cua cay khung for (i = 1; i <= m; ++i){ f >> u >> v; // doc tung canh (u,v) if (Union(u,v)){ ++j; // nhan canh (u,v) vao cay khung khung[j].x = u; khung[j].y = v; if (j == n1) break; } } f.close(); // dong input file // Giai trinh ket qua cout << "\n Cay Khung gom " << n << " dinh, " << j << " canh:"; for (i = 1; i <= j; ++i) cout << endl << khung[i].x << " " << khung[i].y; } main() { CayKhung(); cout << endl << "\n\n F I N I ! \n"; } return 0; Chương trình Pascal (* ---------------------------------------ST.PAS: Thuat toan Kruskal Spaning Tree: Tim cay khung trong do thi lien thong n dinh, m canh 18 ----------------------------------------*) uses crt; const MN = 2001; nl = #13#10; { xuong dong } inf = 'graph.inp'; type canh = record x,y: integer end; var n: integer; { so dinh } m: integer; { so canh } d: array [0..MN] of integer; khung: array[0..MN] of canh; procedure Initd; var i: integer; begin for i := 1 to n do d[i] := i; end; function Find(x: integer): integer; begin while (x <> d[x]) do x := d[x]; Find := x; end; function Union(x, y: integer): integer; begin Union := 0; x := Find(x); y := Find(y); if (x = y) then exit; if (x < y) then d[y] := x else d[x] := y; Union := 1; end; procedure CayKhung; var i, j, u, v, n1: integer; f: text; begin assign(f,inf); reset(f); { mo input file } readln(f,n,m); { doc so dinh n, so canh m } Initd; n1 := n-1; j := 0; { con dem so canh cua cay khung } for i := 1 to m do begin readln(f,u,v); { doc tung canh (u,v) } if Union(u,v) = 1 then begin inc(j); { nap canh (u,v) vao cay khung } khung[j].x := u; khung[j].y := v; if (j = n1) then break; end end; close(f); { dong input file } { Giai trinh ket qua } writeln(nl,' Cay Khung gom ', n ,' dinh, ', j, ' canh:'); for i := 1 to j do writeln(khung[i].x, ' ', khung[i].y); end; BEGIN CayKhung; writeln(nl,' F I N I ! '); 19 readln; END. 1.6 Cây khung cực tiểu Cho đồ thị G vô hướng và liên thông với n đỉnh và m cạnh, cạnh (u,v) có trọng số p(u,v) là một số dương. Cây khung cực tiểu (còn gọi là cây bao trùm ngắn nhất) của G là cây khung với tổng trọng số của các cạnh trong khung là nhỏ nhất. Thuật toán tìm cây khung cực tiểu hoạt động giống thuật toán tìm cây khung với một điểm khác biệt duy nhất là duyệt các cạnh theo trật tự tăng dần của trọng số. • Bước 1. Sắp các cạnh tăng theo trọng số; • Bước 2. Khởi trị với cây khung rỗng; • Bước 3. Duyệt các cạnh theo trật tự đã sắp: nếu cạnh (u,v) không tạo thành chu trình với cây khung thì nạp (u,v) vào cây khung. Điều kiện để cạnh (u,v) không tạo thành chu trình với cây khung là Union(u,v) = 0. Tùy theo các ứng dụng, ta có thể sử dụng trọng số để biểu thị độ dài đường đi giữa hai đỉnh hoặc chi phí phải trả khi đi từ đỉnh này đến đỉnh kia. Ta sử dụng mảng c với mỗi phần tử là một bản ghi gồm 3 trường nguyên x, y và p dùng để chứa các cạnh, trong đó x và y là số hiệu các đỉnh đầu mút của cạnh và p là trọng số của cạnh (x,y) đó. Ngoải ra, ta sử dụng mảng một chiều khung dùng để chứa chỉ số của các cạnh được chọn vào cây khung. struct canh { int x, y, p; } c[MN]; int khung[MN]; // MN la so luong toi da cac canh void CayKhungMin(){ int i, j, n1; int t = 0; // tong trong so ifstream f(inf); // mo input file f >> n >> m; // doc so dinh n, so canh m // doc cac canh vao mang c for(i = 1; i <= m; ++i) f >> c[i].x >> c[i].y >> c[i].p; f.close(); Sort(1,m);// sap tang cac canh theo trong so p Initd(); n1 = n-1; j = 0;// dem so canh cua cay khung for (i = 1; i <= m; ++i){ if (Union(c[i].x,c[i].y)){ ++j; // nap canh i vao cay khung khung[j] = i; // Danh dau canh da chon vao cay khung if (j == n1) break; } } // Giai trinh ket qua cout << "\n Cay Khung cuc tieu gom " << n << " dinh, " << j << " canh:"; for (i = 1; i <= j; ++i) { cout << endl << c[khung[i]].x << " " << c[khung[i]].y; t += c[khung[i]].p; } cout << "\n Tong trong so min: " << t; } Hoạt động của chương trình được minh họa qua thí dụ sau: 20 graph.inp 8 11 1 2 2 1 3 7 1 6 9 2 4 4 2 6 8 3 4 6 4 5 10 5 6 5 5 7 4 5 8 2 7 8 3 Output 5 8 1 2 7 8 2 4 5 6 3 4 2 6 30 Ý nghĩa: Input: Đồ thị có 8 đỉnh và 11 cạnh dạng x y p. Output: 7 cạnh của cây khung cực tiểu (tô đậm) Tổng trọng số min: 30 Chương trình C++ // Devcpp: MST.cpp // Minimal Spaning Tree: Tim cay khung cuc tieu // trong do thi lien thong n dinh, m canh co trong so #include #include #include using namespace std; const int MN = 2001; const char * inf = "graph.inp"; int n; // so dinh int m; // so canh int d[MN]; struct canh { int x, y, p; } c[MN]; int khung[MN]; void Initd() { for (int i = 1; i <= n; ++i) d[i] = i; } int Find(int x) { while (x != d[x]) x = d[x]; return x; } int Union(int x, int y) { x = Find(x); y = Find(y); if (x == y) return 0; if (x < y) d[y] = x; else d[x] = y; return 1; } // Sap cac canh tang theo trong so p void Sort(int dau, int cuoi) { 21 int i = dau, j = cuoi, g = c[(i+j)/2].p; // trong so giua canh tmp; while(i <= j){ while(c[i].p < g) ++i; while(g < c[j].p) --j; if (i <= j){ tmp = c[i]; c[i] = c[j]; c[j] = tmp; ++i; --j; } } if (dau < j) Sort(dau,j); if (i < cuoi) Sort(i,cuoi); } void CayKhungMin(){ int i, j, n1; int t = 0; // tong trong so ifstream f(inf); // mo input file f >> n >> m; // doc so dinh n, so canh m // doc cac canh for(i = 1; i <= m; ++i) f >> c[i].x >> c[i].y >> c[i].p; f.close(); Sort(1,m); Initd(); n1 = n-1; j = 0;// dem so canh cua cay khung for (i = 1; i <= m; ++i){ if (Union(c[i].x,c[i].y)){ ++j; // nap canh i vao cay khung khung[j] = i; if (j == n1) break; } } // Giai trinh ket qua cout << "\n Cay Khung cuc tieu gom " << n << " dinh, " << j << " canh:"; for (i = 1; i <= j; ++i) { cout << endl << c[khung[i]].x << " " << c[khung[i]].y; t += c[khung[i]].p; } cout << "\n Tong trong so min: " << t; } main() { CayKhungMin(); cout << endl << "\n\n F I N I ! \n"; } return 0; Chương trình Pascal (* ---------------------------------------ST.PAS Minimal Spaning Tree: Tim cay khung cuc tieu. trong do thi lien thong n dinh, m canh ------------------------------------------*) uses crt; 22 const MN = 2001; nl = #13#10; { xuong dong } inf = 'graph.inp'; type canh = record x,y,d: integer end; var n: integer; { so dinh } m: integer; { so canh } d: array [0..MN] of integer; c: array[0..MN] of canh; { luu cac canh } khung: array[0..MN] of integer; { luu so hieu canh cua cay khung } procedure Initd; var i: integer; begin for i := 1 to n do d[i] := i; end; function Find(x: integer): integer; begin while (x <> d[x]) do x := d[x]; Find := x; end; function Union(x, y: integer): integer; begin Union := 0; x := Find(x); y := Find(y); if (x = y) then exit; if (x < y) then d[y] := x else d[x] := y; Union := 1; end; { Sap cac canh tang theo trong so p } procedure Sort(dau, cuoi: integer); var i, j, g: integer; { g – trong so giua } tmp: canh; begin i := dau; j := cuoi; g := c[(i+j) div 2].p; while i <= j do begin while c[i].p < g do inc(i); while g < c[j].p do dec(j); if (i <= j) then begin tmp := c[i]; c[i] := c[j]; c[j] := tmp; inc(i); dec(j); end; end; if (dau < j) then Sort(dau,j); if (i < cuoi) then Sort(i,cuoi); end; procedure CayKhungMin; var i, j, n1, t: integer; f: text; begin assign(f,inf); reset(f); { mo input file } readln(f,n,m); { doc so dinh n, so canh m } for i := 1 to m do { doc m canh } readln(f,c[i].x,c[i].y,c[i].p); 23 close(f); Sort(1,m); { sap tang m canh theo trong so p } Initd; n1 := n-1; { so canh cua cay khung } j := 0; { dem so canh cua cay khung } for i := 1 to m do begin { Duyet cac canh theo trat tu da sap } if Union(c[i].x,c[i].y) = 1 then begin inc(j); { Nap canh i vao cay khung } khung[j] := i; if (j = n1) then break; end end; { Giai trinh ket qua } write(nl,' Cay Khung cuc tieu gom ', n, ' dinh, '); writeln(j, ' canh:'); t := 0; { tong trong so cac canh cua cay khung } for i := 1 to j do begin writeln(c[khung[i]].x, ' ', c[khung[i]].y); t := t + c[khung[i]].p; end; writeln(nl,' Tong trong so: ',t); end; BEGIN CayKhungMin; writeln(nl,' F I N I ! '); readln; END. 1.7 Rừng khung Cho G là một đồ thị vô hướng gồm n đỉnh và m cạnh. Hãy xác định các cây khung trong mỗi mảnh liên thông của G. Tập hợp các cây khung đó được gọi là rừng khung của đồ thị G. Hãy liệt kê các cây khung thành phần của rừng khung. 24 graph.inp Ý nghĩa: 8 8 Input: Đồ thị có 8 đỉnh và 8 cạnh. 1 2 Output: Rừng gồm hai cây khung (tô đậm) 1 5 2 5 Cây khung liên thuộc đỉnh 1 gồm 2 cạnh: 3 4 (1,2), (1,5). 3 7 3 8 Cây khung liên thuộc đỉnh 3 gồm 4 cạnh: 4 6 (3,4), (3,7), (3,8), (4,6). 6 8 Thuật toán Để ý rằng dù đồ thị liên thông hay không liên thông thì thủ tục CayKhung như mô tả trong các bài trước đều cho ta một danh sách các cạnh được chọn vào cây khung cần tìm. Danh sách này được ghi trong mảng khung gồm j cạnh. Nếu đồ thị có trên một mảnh liên thông thì ta tách các cạnh của của mảng khung thành các cây con trong rừng cần tìm, mỗi cạnh sẽ được chỉ định rõ là thuộc cây khung của mảnh liên thông nào. Như trong các bài trước, ta qui ước mã số mỗi mảnh liên thông là số hiệu nhỏ nhất của đỉnh thuộc mảnh đó (tức là "nhóm trưởng" của nhóm đó). Cạnh (x,y) thuộc nhóm i khi và chỉ khi Find(x) = i. Vì x và y là cạnh trong một cây khung thành phần nên ta luôn có Find(x) = Find(y). Đó là lí do ta chỉ cần xác định nhóm trưởng cho một trong hai đỉnh x hoặc y. Như vậy, để cho tiện lợi, ta thêm cho dữ liệu mô tả cạnh một trường manh kiểu nguyên dùng để ghi nhận cạnh này thuộc mảnh liên thông nào. struct canh { int x, y, manh; } khung[MN]; Hàm CanhKhung hoạt động như hàm CayKhung trong các bài trước. Hàm cho ra số lượng cạnh được chọn vào rừng khung. int CanhKhung(){ int i, j, u, v, n1; ifstream f(inf); // mo input file f >> n >> m; // doc so dinh n, so canh m Initd(); n1 = n-1; j = 0;// dem so canh cua cay khung for (i = 1; i <= m; ++i){ f >> u >> v; // doc tung canh (u,v) if (Union(u,v)){ ++j; // nhan canh (u,v) vao cay khung khung[j].x = u; khung[j].y = v; if (j == n1) break; } } f.close(); return j; } Bây giờ bạn cài đạt hàm RungKhung. Hàm này duyệt lại các cạnh trong mảng khung và xác định cạnh đó thuộc mảnh liên thông nào. Tiếp đến ta gọi thủ tục Sort để sắp tăng các cạnh theo trường manh. Sau khi sắp, các cạnh thuộc cùng một mảnh liên thông sẽ được xếp cạnh nhau. Việc cuối cùng là giải trình kết quả: hiển thị từng cạnh trong rừng và cho biết cạnh đó thuộc mảnh liên thông nào. Các cạnh trong cùng một mảnh liên thông sẽ tạo thành một cây khung thành phần của mảnh đó. 25 |