2.16 ✅ Hợp nhất - tìm đại diện (Union Find)
- Dùng linh hoạt tư duy Union Find / DSU và nắm vững template. Trong template có 2 cách triển khai:
- Path compression + union by rank
- Đếm số phần tử trong mỗi tập + kích thước tập lớn nhất Mỗi phiên bản phù hợp với từng dạng bài khác nhau.
- Dạng 1 dùng tốt cho các bài: 128, 130, 547, 684, 721, 765, 778, 839, 924, 928, 947, 952, 959, 990.
- Dạng 2 dùng tốt cho các bài: 803, 952. (Bài 803 rất dễ TLE nếu không tối ưu rank/đếm tập.)
- Union Find là một tư duy, không phải lúc nào cũng “nhét template” là xong. Ví dụ bài 399 có thể làm theo kiểu stringUnionFind: mỗi node là chuỗi + map, không chỉ đánh số node bằng
int. - Có bài nếu áp template “cứng” lại không ra. Ví dụ bài 685 không nên dùng path compression/union by rank vì liên quan đồ thị có hướng và cần biết tiền nhiệm của node; nén đường đi sẽ làm mất thông tin cần thiết.
- Biết cách trừu tượng dữ liệu đề bài và đánh số hợp lý, kết hợp
mapđể giảm thời gian (ví dụ bài 721, 959). - Với các bài dạng bản đồ/gạch/lưới, có thể thêm một node đặc biệt và
union()toàn bộ ô ở biên vào node này (ví dụ bài 130, 803). - Nhiều bài dùng Union Find cũng có thể giải bằng DFS/BFS, nhưng thường tốn thời gian hơn.
| STT | Tiêu đề | Lời giải | Độ khó | Độ phức tạp thời gian | Độ phức tạp bộ nhớ | Yêu thích | Tỷ lệ AC (Acceptance) |
|---|---|---|---|---|---|---|---|
| 0128 | Dãy liên tiếp dài nhất (Longest Consecutive Sequence) | Go | Medium | O(n) | O(n) | ❤️ | 48.5% |
| 0130 | Vùng bị bao quanh (Surrounded Regions) | Go | Medium | O(m*n) | O(m*n) | 36.7% | |
| 0200 | Số lượng hòn đảo (Number of Islands) | Go | Medium | O(m*n) | O(m*n) | 57.0% | |
| 0399 | Tính giá trị phép chia (Evaluate Division) | Go | Medium | O(n) | O(n) | 59.6% | |
| 0547 | Số lượng tỉnh thành (Number of Provinces) | Go | Medium | O(n^2) | O(n) | 63.7% | |
| 0684 | Kết nối dư thừa (Redundant Connection) | Go | Medium | O(n) | O(n) | 62.2% | |
| 0685 | Kết nối dư thừa II (Redundant Connection II) | Go | Hard | O(n) | O(n) | 34.1% | |
| 0695 | Diện tích đảo lớn nhất (Max Area of Island) | Go | Medium | 71.8% | |||
| 0721 | Gộp tài khoản (Accounts Merge) | Go | Medium | O(n) | O(n) | ❤️ | 56.3% |
| 0765 | Các cặp đôi nắm tay (Couples Holding Hands) | Go | Hard | O(n) | O(n) | ❤️ | 56.6% |
| 0778 | Bơi trong nước dâng (Swim in Rising Water) | Go | Hard | O(n^2) | O(n) | ❤️ | 59.8% |
| 0785 | Đồ thị có phải lưỡng phân không? (Is Graph Bipartite?) | Go | Medium | 53.1% | |||
| 0803 | Gạch rơi khi bị đánh (Bricks Falling When Hit) | Go | Hard | O(n^2) | O(n) | ❤️ | 34.4% |
| 0839 | Nhóm chuỗi tương tự (Similar String Groups) | Go | Hard | O(n^2) | O(n) | 48.0% | |
| 0924 | Giảm thiểu lây lan mã độc (Minimize Malware Spread) | Go | Hard | O(m*n) | O(n) | 42.1% | |
| 0928 | Giảm thiểu lây lan mã độc II (Minimize Malware Spread II) | Go | Hard | O(m*n) | O(n) | ❤️ | 42.7% |
| 0947 | Loại bỏ nhiều đá nhất với cùng hàng hoặc cột (Most Stones Removed with Same Row or Column) | Go | Medium | O(n) | O(n) | 58.9% | |
| 0952 | Kích thước thành phần lớn nhất theo ước chung (Largest Component Size by Common Factor) | Go | Hard | O(n) | O(n) | ❤️ | 40.0% |
| 0959 | Các vùng bị cắt bởi dấu gạch chéo (Regions Cut By Slashes) | Go | Medium | O(n^2) | O(n^2) | ❤️ | 69.1% |
| 0990 | Khả năng thỏa mãn các phương trình đẳng thức (Satisfiability of Equality Equations) | Go | Medium | O(n) | O(n) | 50.5% | |
| 1020 | Số lượng vùng đất bị cô lập (Number of Enclaves) | Go | Medium | 65.5% | |||
| 1202 | Chuỗi nhỏ nhất sau khi hoán đổi (Smallest String With Swaps) | Go | Medium | 57.7% | |||
| 1254 | Số lượng đảo khép kín (Number of Closed Islands) | Go | Medium | 64.1% | |||
| 1319 | Số thao tác để kết nối mạng (Number of Operations to Make Network Connected) | Go | Medium | 62.1% | |||
| 1579 | Loại bỏ tối đa số cạnh để đồ thị vẫn duyệt được hoàn toàn (Remove Max Number of Edges to Keep Graph Fully Traversable) | Go | Hard | 53.2% | |||
| 1631 | Đường đi với nỗ lực tối thiểu (Path With Minimum Effort) | Go | Medium | 55.7% | |||
| ------------ | ------------------------------------------------------- | ------- | ---------------- | --------------- | ------------- | ------------- | ------------- |