Hai cấu trúc dữ liệu quan trọng

🧩 DSU & Trie: Nhóm liên thông và cây tiền tố

Bài học được tách rõ thành 2 phần độc lập: DSU / Union-Find để quản lý các nhóm rời nhau trong đồ thị, và Trie để lưu, tìm kiếm chuỗi theo tiền tố.

DSUUnion, Find, nhóm liên thông

TrieInsert, Search, Prefix

Mô phỏngChạy từng bước trực quan

Bài tậpTách riêng DSU và Trie

Mục tiêu Tổng quan Phần 1: DSU Phần 2: Trie So sánh Lỗi hay nhầm Bài tập Quiz

Mục tiêu

Sau phần DSU

Hiểu DSU quản lý các tập hợp rời nhau.
Biết dùng find, unite.
Biết tối ưu bằng path compression và union by size/rank.
Ứng dụng đếm nhóm liên thông, kiểm tra cùng nhóm, Kruskal.

Sau phần Trie

Hiểu Trie là cây ký tự.
Biết thêm từ, tìm từ, kiểm tra tiền tố.
Biết khi nào dùng Trie thay cho tìm kiếm chuỗi thông thường.
Ứng dụng gợi ý từ, kiểm tra prefix, dictionary, bitwise trie định hướng nâng cao.

Tổng quan: DSU và Trie khác nhau thế nào?

Cấu trúc	Dùng cho dữ liệu gì?	Thao tác chính	Ứng dụng thường gặp	Không nên nhầm
DSU / Union-Find	Các phần tử thuộc nhiều nhóm rời nhau.	`find(x)`, `unite(a,b)`, kiểm tra cùng nhóm.	Đồ thị vô hướng, nhóm liên thông, Kruskal MST, online connectivity.	DSU không lưu đường đi cụ thể giữa 2 đỉnh.
Trie	Tập các chuỗi/ký tự có chung tiền tố.	`insert(s)`, `search(s)`, `startsWith(prefix)`.	Từ điển, autocomplete, kiểm tra tiền tố, đếm số từ có prefix.	Trie không thay thế mọi bài string; KMP/Z/hash vẫn cần cho tìm mẫu trong văn bản dài.

PHẦN 1

DSU / Union-Find

DSU quản lý các tập hợp rời nhau. Mỗi phần tử có một “đại diện nhóm” gọi là root. Khi nối hai phần tử, ta gộp hai nhóm lại.

find(x)

Tìm đại diện nhóm của x.

unite(a,b)

Gộp nhóm chứa a và nhóm chứa b.

same(a,b)

Kiểm tra find(a) == find(b).

1.1. Mô phỏng DSU

Nhấn “Bước tiếp” để xem DSU gộp nhóm.

1.2. Code DSU chuẩn hiện đại

#include 
using namespace std;

struct DSU {
    vector parent, sz;

    DSU(int n) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]); // path compression
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;

        if (sz[a] < sz[b]) swap(a, b);     // union by size
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    DSU dsu(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        dsu.unite(u, v);
    }

    int components = 0;
    for (int i = 1; i <= n; i++) {
        if (dsu.find(i) == i) components++;
    }

    cout << components;
    return 0;
}

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        if x == self.parent[x]:
            return x
        self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

    def same(self, a, b):
        return self.find(a) == self.find(b)

n, m = map(int, input().split())
dsu = DSU(n)
for _ in range(m):
    u, v = map(int, input().split())
    dsu.unite(u, v)
components = sum(1 for i in range(1, n + 1) if dsu.find(i) == i)
print(components)

Ghi nhớ DSU: nếu đề có “nối hai phần tử”, “kiểm tra cùng nhóm”, “đếm số nhóm”, hãy nghĩ tới DSU.

PHẦN 2

Trie / Prefix Tree

Trie là cây ký tự. Mỗi cạnh/nút tương ứng một ký tự. Các từ có chung tiền tố sẽ đi chung một đoạn đường trong cây.

insert(s)

Thêm chuỗi s vào Trie.

search(s)

Kiểm tra chuỗi s có phải một từ hoàn chỉnh không.

startsWith(p)

Kiểm tra có từ nào bắt đầu bằng tiền tố p không.

2.1. Mô phỏng Trie

Danh sách từTừ / tiền tố cần kiểm tra

Nhấn “Dựng Trie” để xem cây ký tự.

2.2. Code Trie rõ ràng

class TrieNode:
    def __init__(self):
        self.child = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, s):
        node = self.root
        for c in s:
            if c not in node.child:
                node.child[c] = TrieNode()
            node = node.child[c]
        node.end = True

    def search(self, s):
        node = self.root
        for c in s:
            if c not in node.child:
                return False
            node = node.child[c]
        return node.end

    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.child:
                return False
            node = node.child[c]
        return True

trie = Trie()
for word in ["cat", "car", "dog"]:
    trie.insert(word)
print(trie.search("car"))       # True
print(trie.starts_with("ca"))   # True
print(trie.search("ca"))        # False

#include 
using namespace std;

struct Trie {
    struct Node {
        int child[26];
        bool end;
        Node() {
            memset(child, -1, sizeof(child));
            end = false;
        }
    };

    vector nodes;
    Trie() { nodes.push_back(Node()); }

    void insert(const string& s) {
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (nodes[cur].child[c] == -1) {
                nodes[cur].child[c] = nodes.size();
                nodes.push_back(Node());
            }
            cur = nodes[cur].child[c];
        }
        nodes[cur].end = true;
    }

    bool search(const string& s) {
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (nodes[cur].child[c] == -1) return false;
            cur = nodes[cur].child[c];
        }
        return nodes[cur].end;
    }

    bool startsWith(const string& prefix) {
        int cur = 0;
        for (char ch : prefix) {
            int c = ch - 'a';
            if (nodes[cur].child[c] == -1) return false;
            cur = nodes[cur].child[c];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("dog");
    cout << trie.search("car") << "\
";
    cout << trie.startsWith("ca") << "\
";
    return 0;
}

Ghi nhớ Trie: nếu bài có nhiều từ và nhiều truy vấn tiền tố, Trie thường hiệu quả hơn tìm tuyến tính từng từ.

Khi nào dùng DSU, khi nào dùng Trie?

Chọn DSU nếu đề có

Nối hai đỉnh / hai người / hai máy tính vào cùng nhóm.
Hỏi hai phần tử có cùng nhóm không.
Đếm số nhóm liên thông sau nhiều thao tác nối.
Kruskal: chọn cạnh để xây cây khung nhỏ nhất.

Chọn Trie nếu đề có

Thêm nhiều từ vào từ điển.
Hỏi một từ có tồn tại không.
Hỏi có từ nào bắt đầu bằng tiền tố không.
Đếm số từ có cùng prefix hoặc gợi ý autocomplete.

Lỗi học sinh hay nhầm

DSU: quên gọi find trước khi unite.
Phải gộp hai root, không gộp trực tiếp hai đỉnh chưa tìm đại diện.

DSU: không path compression.
Code vẫn có thể đúng nhưng chậm hơn nhiều ở test lớn.

Trie: nhầm search với startsWith.
search("ca") có thể sai, nhưng startsWith("ca") đúng nếu có từ “cat”, “car”.

Trie: không đánh dấu end.
Nếu không có end, sẽ không phân biệt được “car” là từ hoàn chỉnh hay chỉ là tiền tố.

Bài tập luyện tập tách riêng

📘 DSU - Cơ bản

Đếm số nhóm liên thông trong đồ thị vô hướng.
Kiểm tra hai đỉnh u, v có cùng component không.
Sau mỗi thao tác nối, in số nhóm còn lại.

📗 DSU - Nâng cao

Kruskal tìm cây khung nhỏ nhất.
Phát hiện cạnh tạo chu trình trong đồ thị vô hướng.
Offline query dạng nối cạnh và hỏi connectivity.

📙 Trie - Cơ bản

Thêm danh sách từ và kiểm tra một từ có tồn tại không.
Kiểm tra có từ nào bắt đầu bằng prefix p không.
Đếm số từ có cùng tiền tố.

🐉 Trie - HSG định hướng

Autocomplete: in tối đa 10 từ bắt đầu bằng prefix.
Đếm số từ có cùng tiền tố dài nhất.
Bitwise Trie tìm XOR lớn nhất.

Quiz kiểm tra nhanh

Câu 1. DSU phù hợp nhất với dạng bài nào?

Câu 2. Trong Trie, biến end dùng để làm gì?

Câu 3. search("ca") và startsWith("ca") khác nhau thế nào?

Tổng kết

DSU dùng để quản lý nhóm rời nhau và trả lời nhanh các câu hỏi liên thông. Trie dùng để lưu chuỗi theo tiền tố và tìm kiếm từ/prefix nhanh. Hai phần này nên học tách rõ để tránh nhầm giữa bài đồ thị và bài xử lý chuỗi.