Trie និង Union-Find

មាតិកា

1. អ្នកឯកទេសពីរ
2. បញ្ហានៃការស្វែងរក Prefix
3. Trie មើលទៅដូចម្តេច
4. សាងសង់ Trie
5. Autocomplete
6. ថ្លៃ និងការដោះដូររបស់ Trie
7. បញ្ហាការដាក់ក្រុម
8. Union-Find៖ កំណែសាមញ្ញ
9. Path Compression និង Union by Rank
10. Connected Component និង Edge ដែលហួសចាំបាច់
11. រូបមន្ត៖ trie.ts និង union-find.ts សម្រាប់ algolab
12. សាកល្បងដោយខ្លួនឯង

1. អ្នកឯកទេសពីរ

structure ភាគច្រើនដែលយើងបានរៀនមកទល់ពេលនេះគឺជាអ្នកទូទៅ។ Array, hash map, tree និង graph លេចឡើងស្ទើរតែគ្រប់កម្មវិធី។ ជំពូកនេះគ្របដណ្តប់អ្នកឯកទេសពីរ។ ម្នាក់ៗធ្វើការងារតែមួយបានល្អខ្លាំងដែលគួរស្គាល់តាមឈ្មោះ៖

• Trie (ប្រកាសថា "try" មកពី retrieval) រក្សាទុក string ច្រើន ដើម្បីឲ្យ "អ្វីៗទាំងអស់ដែលចាប់ផ្តើមដោយ ca" លឿន។ វាជំរុញ autocomplete, spell checker និង routing table នៅខាងក្នុង web framework ជាច្រើន។
• Union-find (ហៅម្យ៉ាងទៀតថា disjoint-set union ឬ DSU) តាមដានថាធាតុណាជាកម្មសិទ្ធិរបស់ក្រុមតែមួយ ហើយបញ្ចូលក្រុមបានលឿន។ វាឆ្លើយ "តើទាំងពីរនេះភ្ជាប់គ្នាទេ?" ក្នុងពេលស្ទើរតែថេរ។ អ្នកជួបវាក្នុង network connectivity, ក្រុមមិត្តភក្តិ, image segmentation និង algorithm minimum-spanning-tree របស់ Kruskal។

គ្មានមួយណាចម្លែកទេ។ ប្រអប់ស្វែងរកដែលមានការណែនាំគឺជាបញ្ហា trie។ "តើអ្នកប្រើពីរនាក់នេះនៅក្នុងក្រុមតែមួយបន្ទាប់ពីការបញ្ចូលទាំងនេះឬទេ?" គឺជាបញ្ហា union-find។ ទាំងពីរក៏ជាចំណូលចិត្តក្នុងការសម្ភាសន៍ផងដែរ ព្រោះល្បិចនៅពីក្រោយមួយៗខ្លីនិងឆើតឆាយ។

2. បញ្ហានៃការស្វែងរក Prefix

អ្នកកំពុងសាងសង់ប្រអប់ស្វែងរក។ អ្នកប្រើវាយ ca ហើយអ្នកចង់បង្ហាញពាក្យដែលចាប់ផ្តើមដោយវា។ អ្នកមានពាក្យ 100,000។ ដំណោះស្រាយជាក់ស្តែង៖

function startingWith(words: string[], prefix: string): string[] {
  return words.filter((w) => w.startsWith(prefix));
}

const words = ["car", "card", "care", "cat", "dog"];
console.log(startingWith(words, "ca"));
// [ 'car', 'card', 'care', 'cat' ]

វាដំណើរការ ប៉ុន្តែវាមើល រាល់ ពាក្យនៅរាល់ការចុចគ្រាប់ចុច។ នោះគឺ O(n × L) ដែល n ជាចំនួនពាក្យ ហើយ L ជាប្រវែង prefix។ ជាមួយពាក្យ 100,000 និងការចុចគ្រាប់ចុចរៀងរាល់ 100 ms អ្នកកំពុងធ្វើការងារដដែលៗច្រើន ដើម្បីឆ្លើយសំណួរដែលចម្លើយស្ទើរតែមិនប្តូររវាងការចុចគ្រាប់ចុច។

តើ hash map អាចជួយបានទេ? Set ឆ្លើយ "តើ car ជាពាក្យឬទេ?" ក្នុង O(1) ប៉ុន្តែវាមិនអាចឆ្លើយ "ពាក្យណាខ្លះចាប់ផ្តើមដោយ ca?" ដោយមិនស្កេនអ្វីៗទាំងអស់ទេ។ Hash ធ្វើឲ្យពាក្យច្របល់ ដូច្នេះអ្នកជិតខាងបាត់បង់។

Array ដែលបានតម្រៀបបូករួមនឹង binary search (ជំពូកទី 7) រកឃើញពាក្យ ដំបូង ដែលមាន prefix ក្នុង O(L log n) ហើយពាក្យដែលត្រូវគ្នានៅជាប់គ្នា។ នោះល្អ ប៉ុន្តែការបញ្ចូលពាក្យថ្មីមានថ្លៃ O(n) ដោយសារការរុញដែលអ្នកបានរៀនក្នុងជំពូក array។

Trie ផ្តល់ការស្វែងរក prefix លឿន និង ការបញ្ចូលថោក។

3. Trie មើលទៅដូចម្តេច

Trie គឺជា tree ដែល edge នីមួយៗជា អក្សរ។ ពាក្យមួយគឺជា path ពី root ចុះទៅ node ដែលមានសម្គាល់។ ពាក្យដែលចែករំលែកការចាប់ផ្តើមចែករំលែក path។ នេះគឺ car, card, care, cat និង dog៖

(root)
 ├─ c
 │   └─ a
 │       ├─ r *        <- "car" ends here
 │       │   ├─ d *    <- "card"
 │       │   └─ e *    <- "care"
 │       └─ t *        <- "cat"
 └─ d
     └─ o
         └─ g *        <- "dog"

* សម្គាល់ថា "ពាក្យមួយបញ្ចប់នៅទីនេះ"។ យើងត្រូវការវា ព្រោះ car ជាទាំងពាក្យ និងជាការចាប់ផ្តើមនៃ card។ បើគ្មានសម្គាល់ យើងមិនអាចប្រាប់ថា car ត្រូវបានរក្សាទុក ខណៈ ca មិនមែនទេ។

សូមកត់សម្គាល់ការសន្សំ៖ car, card និង care រក្សាទុកអក្សរ c, a, r តែ ម្តង។ ហើយដើម្បីរកអ្វីៗទាំងអស់ដែលចាប់ផ្តើមដោយ ca អ្នកដើរពីរជំហាន (c បន្ទាប់មក a) ហើយបន្ទាប់មកអ្វីៗទាំងអស់នៅក្រោម node នោះគឺជាចម្លើយ។ អ្នកមិនមើល dog ទាល់តែសោះ។

រាល់ជំហានចុះក្រោមគឺជាការរកមើលអក្សរមួយក្នុងចំណោម child របស់ node។ យើងរក្សាទុក child ក្នុង Map ដូច្នេះរាល់ជំហានគឺ O(1)។

4. សាងសង់ Trie

Node នីមួយៗត្រូវការពីរយ៉ាង៖ child របស់វា (អក្សរទៅ node) និង flag ដែលប្រាប់ថាតើពាក្យមួយបញ្ចប់នៅទីនេះឬទេ។

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}

ខ្លួន trie គ្រាន់តែជា root node បូក method។ Insert ដើរចុះតាមពាក្យ បង្កើត node ដែលបាត់ពេលដើរ បន្ទាប់មកសម្គាល់ node ចុងក្រោយ៖

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      let next = node.children.get(ch);
      if (!next) {
        next = new TrieNode();
        node.children.set(ch, next);
      }
      node = next;
    }
    node.isWord = true;
  }
}

ទាំង has និង startsWith ត្រូវដើរចុះតាម string ហើយរាយការណ៍កន្លែងដែលពួកវាបញ្ចប់។ យើងសរសេរការដើរនោះម្តង ជា private helper៖

  private find(prefix: string): TrieNode | undefined {
    let node: TrieNode | undefined = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return undefined;
    }
    return node;
  }

  has(word: string): boolean {
    return this.find(word)?.isWord === true;
  }

  startsWith(prefix: string): boolean {
    return this.find(prefix) !== undefined;
  }

ភាពខុសគ្នារវាងពីរនេះគឺជាចំណុចទាំងមូលនៃ flag isWord។ has("ca") ដើរតាម path បានល្អ ប៉ុន្តែ node មិនមានសម្គាល់ ដូច្នេះចម្លើយគឺ false។ startsWith("ca") ខ្វល់តែថា path មាន ដូច្នេះចម្លើយគឺ true។

ជាមួយ car, card, care, careful, cat និង dog ដែលបានបញ្ចូល៖

console.log(t.has("car"));        // true
console.log(t.has("ca"));         // false
console.log(t.startsWith("ca"));  // true
console.log(t.startsWith("cx"));  // false

រាល់ប្រតិបត្តិការប៉ះ node មួយក្នុងមួយអក្សរ។ ថ្លៃអាស្រ័យលើ ប្រវែងនៃពាក្យ មិនមែនលើចំនួនពាក្យដែលបានរក្សាទុកទេ។ Trie ដែលមានពាក្យដប់ និង trie ដែលមានពាក្យដប់លាន ឆ្លើយ has("car") ក្នុងបីជំហានដូចគ្នា។

5. Autocomplete

ដើម្បីណែនាំការបំពេញ ដើរចុះទៅ node សម្រាប់ prefix បន្ទាប់មក ប្រមូលរាល់ពាក្យនៅក្រោមវា ដោយ depth-first search (ជំពូកទី 9) ដោយកាន់អក្សរដែលបានមកដល់ពេលនេះ៖

  suggest(prefix: string, limit = Infinity): string[] {
    const start = this.find(prefix);
    const out: string[] = [];
    if (!start) return out;

    const walk = (node: TrieNode, path: string): void => {
      if (out.length >= limit) return;
      if (node.isWord) out.push(path);
      const keys = [...node.children.keys()].sort();
      for (const k of keys) walk(node.children.get(k)!, path + k);
    };

    walk(start, prefix);
    return out;
  }

ព័ត៌មានលម្អិតបីដែលគួរកត់សម្គាល់៖

• ប្រសិនបើ prefix មិនមាន find ត្រឡប់ undefined ហើយយើងត្រឡប់បញ្ជីទទេភ្លាមៗ។ គ្មានការស្កេន។
• យើងពិនិត្យ node.isWord មុន ពេលទស្សនា child។ នោះគឺជាការដើរ preorder ដូច្នេះពាក្យខ្លី (car) មកមុនពាក្យវែង (card)។
• យើងតម្រៀបអក្សរ child ដូច្នេះការណែនាំចេញមកតាមលំដាប់អក្ខរក្រម។ limit បញ្ឈប់មុនកំណត់ ដែលមានសារៈសំខាន់៖ ប្រអប់ស្វែងរកចង់បានការណែនាំ 5 ដំបូង មិនមែន 50,000 ទេ។

console.log(t.suggest("car"));
// [ 'car', 'card', 'care', 'careful' ]

console.log(t.suggest("ca", 3));
// [ 'car', 'card', 'care' ]

console.log(t.suggest("x"));
// []

Autocomplete ពិតជាធម្មតាចាត់ថ្នាក់ការណែនាំតាមប្រជាប្រិយភាព មិនមែនតាមអក្ខរក្រមទេ។ ការធ្វើឲ្យប្រសើរឡើងទូទៅគឺរក្សាទុកចំនួនក្នុង node ដែលមានសម្គាល់នីមួយៗ បន្ទាប់មកប្រើ heap (ជំពូកទី 10) ដើម្បីរក្សា K លទ្ធផលកំពូល។ រចនាសម្ព័ន្ធនៅដដែល។

6. ថ្លៃ និងការដោះដូររបស់ Trie

ឲ្យ L ជាប្រវែងនៃពាក្យ ឬ prefix ហើយ k ជាចំនួនការណែនាំដែលអ្នកប្រមូល។

ការ hash string អានគ្រប់តួអក្សរ ដូច្នេះការរកមើល hash set ក៏ជា O(L) ដែរ។ Trie មិនលឿនជាងសម្រាប់ការផ្គូផ្គងពិតប្រាកដទេ។ ជ័យជម្នះរបស់វាគឺសំណួរ prefix។

ថ្លៃគឺអង្គចងចាំ។ Node នីមួយៗជា object ដែលកាន់ Map។ Trie លើបញ្ជីពាក្យធំអាចប្រើអង្គចងចាំច្រើនជាងពាក្យដូចគ្នាក្នុង Set ច្រើនណាស់។ វិធីកាត់បន្ថយ៖

• Compressed trie (radix tree) បញ្ចូលច្រវាក់នៃ node ដែលមាន child តែមួយចូលទៅជា edge តែមួយដែលដាក់ស្លាក "reful"។ HTTP router ជាច្រើនប្រើវា។
• សម្រាប់តែអក្សរតូច a-z node នីមួយៗអាចកាន់ array ថេរនៃ child 26 ជំនួសឲ្យ Map។ នោះលឿនជាង ប៉ុន្តែខ្ជះខ្ជាយទំហំលើ node ដែលស្រួយ។
• ប្រសិនបើអ្នកត្រូវការត្រឹមតែ string ពីរបីពាន់ array ធម្មតាដែលបានតម្រៀប និង startsWith គឺសាមញ្ញជាង ហើយលឿនគ្រប់គ្រាន់។ ប្រើ trie នៅពេលបញ្ជីពាក្យធំ ប្តូរប្រែ ឬ prefix ត្រូវបានសួរជាប់ជានិច្ច។

កន្លែងផ្សេងទៀតដែល trie លេចឡើង៖ spell checker ("តើអ្នកមានន័យថា...?") IP routing (longest-prefix match លើខ្ទង់ binary) ក្តារចុចទូរស័ព្ទ T9 និងល្បែងពាក្យដូចជា Boggle ដែលអ្នកកាត់ការស្វែងរកភ្លាមនៅពេលគ្មានពាក្យចាប់ផ្តើមដោយអក្សរបច្ចុប្បន្ន។

7. បញ្ហាការដាក់ក្រុម

ឥឡូវបញ្ហាប្រភេទផ្សេង។ អ្នកមានកុំព្យូទ័រ 10 ក្នុងបណ្តាញមួយ។ ខ្សែកាបត្រូវបានដោតម្តងមួយ។ បន្ទាប់ពីខ្សែនីមួយៗ អ្នកត្រូវបានសួរ៖ "តើកុំព្យូទ័រទី 3 អាចទៅដល់កុំព្យូទ័រទី 8 ទេ?"

អ្នកអាចធ្វើគំរូនេះជា graph (ជំពូកទី 11) ហើយដំណើរការ BFS សម្រាប់រាល់សំណួរ។ នោះមានថ្លៃ O(V + E) ក្នុងមួយសំណួរ។ ប្រសិនបើមានខ្សែកាបមួយលាន និងសំណួរមួយលាន នោះយឺតពេក។

ប៉ុន្តែសូមកត់សម្គាល់អ្វីដែលយើងពិតជាត្រូវដឹង។ យើងមិនត្រូវការ path ទេ គ្រាន់តែថាតើកុំព្យូទ័រទាំងពីរនៅក្នុង ក្រុមតែមួយ ឬអត់។ ហើយក្រុមតែងតែ បញ្ចូលគ្នា ប៉ុណ្ណោះ ខ្សែកាបមិនដែលបំបែកក្រុមឡើយ។

នោះហើយជាការងារពិតប្រាកដរបស់ union-find។ វាគាំទ្រប្រតិបត្តិការពីរ៖

• union(a, b)៖ បញ្ចូលក្រុមរបស់ a ជាមួយក្រុមរបស់ b។
• find(a)៖ ត្រឡប់ តំណាង (ហៅថា "root") សម្រាប់ក្រុមរបស់ a។ ធាតុពីរនៅក្នុងក្រុមតែមួយនៅពេលពួកវាមានតំណាងដូចគ្នា។

កន្លែងដែលអ្នកជួបវានៅកន្លែងធ្វើការ៖

• បណ្តាញ៖ តើម៉ាស៊ីនពីរភ្ជាប់គ្នាបន្ទាប់ពី link ទាំងនេះឬទេ?
• មុខងារសង្គម៖ ក្រុមមិត្តភក្តិ ចង្កោម "មនុស្សដែលអ្នកប្រហែលស្គាល់"។
• ការកែរូបភាព៖ ឧបករណ៍ធុងថ្នាំលាបរកតំបន់ដែលភ្ជាប់គ្នានៃ pixel ស្រដៀងគ្នា។
• Algorithm របស់ Kruskal៖ សាងសង់បណ្តាញថោកបំផុតដោយបន្ថែម edge ថោកបំផុតដែលមិនបង្កើត cycle។ Union-find រកឃើញ cycle។
• សមមូល៖ "account ពីរនេះជាមនុស្សតែមួយ" ការបញ្ចូលក្នុងការសម្អាតទិន្នន័យ។

8. Union-Find៖ កំណែសាមញ្ញ

គំនិតគឺ៖ ធាតុនីមួយៗចង្អុលទៅ parent។ ការតាម parent នាំទៅ root ដែលជាធាតុដែលចង្អុលទៅខ្លួនឯង។ Root គឺជាតំណាងរបស់ក្រុម។

ចាប់ផ្តើមជាមួយធាតុ 6 ម្នាក់ៗក្នុងក្រុមផ្ទាល់ខ្លួន ម្នាក់ៗជា parent របស់ខ្លួន៖

parent = [0, 1, 2, 3, 4, 5]

union(0, 1) រក root របស់ 0 និង 1 បន្ទាប់មកធ្វើឲ្យមួយចង្អុលទៅមួយទៀត៖ parent[1] = 0។

parent = [0, 0, 2, 3, 4, 5]     groups: {0,1} {2} {3} {4} {5}

union(1, 2)៖ root របស់ 1 គឺ 0, root របស់ 2 គឺ 2។ ចង្អុល 2 ទៅ 0៖

parent = [0, 0, 0, 3, 4, 5]     groups: {0,1,2} {3} {4} {5}

កំណែដំបូងក្នុងកូដ៖

function find(parent: number[], x: number): number {
  while (parent[x] !== x) x = parent[x];
  return x;
}

function union(parent: number[], a: number, b: number): void {
  parent[find(parent, a)] = find(parent, b);
}

នេះត្រឹមត្រូវ ប៉ុន្តែវាមានបញ្ហាលាក់កំបាំង។ Union ធាតុតាមលំដាប់មិនល្អ ហើយ link របស់ parent បង្កើតជា ច្រវាក់វែង ដែលជា linked list ក្លែងខ្លួន៖

const parent = Array.from({ length: 5 }, (_, i) => i);
for (let i = 0; i < 4; i++) union(parent, i, i + 1);
console.log(parent); // [ 1, 2, 3, 4, 4 ]

នៅទីនេះ 0 -> 1 -> 2 -> 3 -> 4។ ឥឡូវ find(0) ដើរកាត់ច្រវាក់ទាំងមូល ដែលជា O(n)។ ជាមួយធាតុមួយលាន រាល់សំណួរយឺត។ គំនិតតូចពីរដោះស្រាយវា។

9. Path Compression និង Union by Rank

គំនិតទី 1៖ path compression។ ខណៈពេលដើរឡើងទៅ root ក្នុង find ធ្វើឲ្យរាល់ធាតុដែលអ្នកឆ្លងកាត់ចង្អុលទៅ grandparent (ឬដោយផ្ទាល់ទៅ root)។ find បន្ទាប់លើ path នោះខ្លីជាង។ Tree ធ្វើឲ្យខ្លួនវាសំប៉ែតតាមពេលវេលា ដោយឥតគិតថ្លៃ ជាផលរំលេចនៃការសួរសំណួរ។

គំនិតទី 2៖ union by rank។ នៅពេលបញ្ចូល tree ពីរ ភ្ជាប់ tree ដែល ទាបជាង នៅក្រោម tree ដែល ខ្ពស់ជាង មិនមែនផ្ទុយទេ។ យើងរក្សាលេខ rank សម្រាប់ root នីមួយៗ ដែលជាព្រំខាងលើនៃកម្ពស់ tree របស់វា។ ប្រសិនបើ rank ស្មើគ្នា រើសមួយណាក៏បាន ហើយបង្កើន rank របស់វាមួយ។

រួមគ្នា ពីរនេះធ្វើឲ្យថ្លៃក្នុងមួយប្រតិបត្តិការ ស្ទើរតែ O(1)។ ព្រំត្រឹមត្រូវគឺ O(α(n)) ដែល α ជា inverse Ackermann function។ វាលូតលាស់យឺតណាស់ ដែលវានៅក្រោម 5 សម្រាប់ n ណាមួយដែលអ្នកនឹងរក្សាទុក សូម្បីតែច្រើនជាងចំនួនអាតូមក្នុងសកលលោក។ ក្នុងការអនុវត្ត អ្នកអាចអានវាថា "ថេរ"។

នេះគឺជា class ពេញលេញ៖

class UnionFind {
  private parent: number[];
  private rank: number[];
  count: number; // number of separate groups

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;
  }

  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // path halving
      x = this.parent[x];
    }
    return x;
  }

  union(a: number, b: number): boolean {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false; // already in the same group

    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
    else {
      this.parent[rb] = ra;
      this.rank[ra]++;
    }
    this.count--;
    return true;
  }

  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

កំណត់សម្គាល់មួយចំនួនអំពីកូដ៖

• បន្ទាត់ this.parent[x] = this.parent[this.parent[x]] ហៅថា path halving។ វាជាបងប្អូនជីដូនមួយដែលប្រើ loop នៃ path compression៖ រាល់ជំហានធ្វើឲ្យ x រំលងមួយកម្រិត។ វាជៀសវាង recursion ដូច្នេះមិនបារម្ភ stack overflow លើ tree ជ្រៅខ្លាំងទេ។
• union ត្រឡប់ true នៅពេលវាបញ្ចូលក្រុមពីរ និង false នៅពេលពួកវាបានរួមគ្នារួចហើយ។ តម្លៃត្រឡប់តូចនោះមានប្រយោជន៍គួរឲ្យភ្ញាក់ផ្អើល ដូចដែលផ្នែកបន្ទាប់បង្ហាញ។
• count ចាប់ផ្តើមនៅ n ហើយថយចុះមួយរាល់ការបញ្ចូលដែលជោគជ័យ។ វាគឺជាចំនួនក្រុមបច្ចុប្បន្នជានិច្ច ក្នុង O(1)។

ការប្រើវា៖

const uf = new UnionFind(6);
console.log(uf.count);                                  // 6
console.log(uf.union(0, 1), uf.union(1, 2), uf.union(0, 2));
// true true false
console.log(uf.connected(0, 2), uf.connected(0, 5), uf.count);
// true false 4

union(0, 2) ទីបីត្រឡប់ false ព្រោះ 0 និង 2 ត្រូវបានភ្ជាប់រួចហើយតាមរយៈ 1។ បន្ទាប់ពីការបញ្ចូលពិតពីរដង ក្រុមប្រាំមួយបានក្លាយជាបួន។

Union-find មានដែនកំណត់មួយ៖ វាមិនអាច បំបែក ក្រុមបានទេ។ វាក៏មិនចងចាំ path រវាងធាតុពីរដែរ គ្រាន់តែថាតើពួកវាភ្ជាប់គ្នាឬអត់។ ប្រសិនបើអ្នកត្រូវការមួយណាមួយ ត្រូវប្រើ graph។

10. Connected Component និង Edge ដែលហួសចាំបាច់

នេះគឺជាបញ្ហាសម្ភាសន៍បុរាណពីរដែល union-find ដោះស្រាយក្នុងប៉ុន្មានបន្ទាត់។

ចំនួន connected component។ អ្នកមាន node n ដាក់លេខពី 0 ដល់ n - 1 និងបញ្ជី edge undirected។ តើមានក្រុមដាច់ពីគ្នាប៉ុន្មាន?

function countComponents(n: number, edges: [number, number][]): number {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) uf.union(a, b);
  return uf.count;
}

console.log(countComponents(5, [[0, 1], [1, 2], [3, 4]])); // 2
console.log(countComponents(6, [[0, 1], [1, 2], [3, 4]])); // 3

ក្នុងការហៅលើកដំបូង {0,1,2} និង {3,4} បង្កើតជា 2 ក្រុម។ ក្នុងលើកទីពីរ node 5 គ្មាន edge ហើយនៅម្នាក់ឯង ដូច្នេះមាន 3 ក្រុម។ អ្នកក៏អាចដោះស្រាយវាដោយ DFS ពីជំពូកទី 11 បានដែរ។ Union-find ពូកែនៅពេល edge មកដល់ ម្តងមួយ ហើយអ្នកត្រូវការចម្លើយបន្ទាប់ពីម្តងៗ ព្រោះ count ទាន់សម័យជានិច្ច។

Redundant connection។ បណ្តាញមួយចាប់ផ្តើមជា tree ដែលមាន node 1 ដល់ n ជាមួយ link n - 1។ បន្ទាប់មក link បន្ថែមមួយត្រូវបានបន្ថែម បង្កើត cycle។ រក link ដែលជាអ្នកបន្ថែម៖ edge ដំបូងក្នុងបញ្ជីដែលចុងទាំងពីររបស់វា ត្រូវបានភ្ជាប់រួចហើយ។

function findRedundantEdge(
  edges: [number, number][],
): [number, number] | null {
  const uf = new UnionFind(edges.length + 1); // nodes are 1..n
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return [a, b];
  }
  return null;
}

console.log(findRedundantEdge([[1, 2], [1, 3], [2, 3]]));
// [ 2, 3 ]
console.log(findRedundantEdge([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]));
// [ 1, 4 ]

ក្នុងឧទាហរណ៍ទីមួយ link 1-2 និង 1-3 ភ្ជាប់អ្វីៗទាំងអស់។ Link 2-3 ភ្ជាប់ node ពីរដែលនៅក្នុងក្រុមតែមួយរួចហើយ ដូច្នេះវាបិទ cycle។ ក្នុងឧទាហរណ៍ទីពីរ 1-2, 2-3, 3-4 សាងសង់ច្រវាក់ ហើយ 1-4 ភ្ជាប់ចុងទាំងពីរនៃវា។ នេះគឺជាមូលហេតុពិតប្រាកដដែល union ត្រឡប់ boolean៖ "តើ edge នេះភ្ជាប់ក្រុម ផ្សេងគ្នា ពីរឬទេ?" គឺជាសំណួរដូចគ្នានឹង "តើ edge នេះ ជៀសវាង cycle ឬទេ?"។ Algorithm របស់ Kruskal ប្រើការពិនិត្យដូចគ្នាដើម្បីជ្រើស edge។

តើអ្នកសម្គាល់បញ្ហា union-find យ៉ាងដូចម្តេច? រកមើលសញ្ញាទាំងនេះ៖

• "តើ X និង Y ភ្ជាប់ / ក្នុងក្រុមតែមួយ / សមមូលឬទេ?"
• ក្រុម បញ្ចូលគ្នា ប៉ុណ្ណោះតាមពេលវេលា មិនដែលបំបែក។
• អ្នកត្រូវការ ចំនួនក្រុម ឬ ទំហំ នៃក្រុមធំបំផុត។
• Edge ឬទំនាក់ទំនងមកដល់ជាស្ទ្រីម។

11. រូបមន្ត៖ trie.ts និង union-find.ts សម្រាប់ algolab

បន្ថែម module trie។ បង្កើត src/trie.ts៖

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}

export class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      let next = node.children.get(ch);
      if (!next) {
        next = new TrieNode();
        node.children.set(ch, next);
      }
      node = next;
    }
    node.isWord = true;
  }

  private find(prefix: string): TrieNode | undefined {
    let node: TrieNode | undefined = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return undefined;
    }
    return node;
  }

  has(word: string): boolean {
    return this.find(word)?.isWord === true;
  }

  startsWith(prefix: string): boolean {
    return this.find(prefix) !== undefined;
  }

  suggest(prefix: string, limit = Infinity): string[] {
    const start = this.find(prefix);
    const out: string[] = [];
    if (!start) return out;

    const walk = (node: TrieNode, path: string): void => {
      if (out.length >= limit) return;
      if (node.isWord) out.push(path);
      const keys = [...node.children.keys()].sort();
      for (const k of keys) walk(node.children.get(k)!, path + k);
    };

    walk(start, prefix);
    return out;
  }
}

បន្ថែម module union-find។ បង្កើត src/union-find.ts៖

export class UnionFind {
  private parent: number[];
  private rank: number[];
  count: number;

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;
  }

  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }

  union(a: number, b: number): boolean {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false;

    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
    else {
      this.parent[rb] = ra;
      this.rank[ra]++;
    }
    this.count--;
    return true;
  }

  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

export function countComponents(
  n: number,
  edges: [number, number][],
): number {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) uf.union(a, b);
  return uf.count;
}

export function findRedundantEdge(
  edges: [number, number][],
): [number, number] | null {
  const uf = new UnionFind(edges.length + 1);
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return [a, b];
  }
  return null;
}

ឥឡូវ test។ បង្កើត src/trie.test.ts៖

import { test } from "node:test";
import assert from "node:assert/strict";
import { Trie } from "./trie.ts";

function build(): Trie {
  const t = new Trie();
  for (const w of ["car", "card", "care", "careful", "cat", "dog"]) {
    t.insert(w);
  }
  return t;
}

test("has distinguishes words from prefixes", () => {
  const t = build();
  assert.equal(t.has("car"), true);
  assert.equal(t.has("ca"), false);
  assert.equal(t.has("cars"), false);
});

test("startsWith checks the path only", () => {
  const t = build();
  assert.equal(t.startsWith("ca"), true);
  assert.equal(t.startsWith("cx"), false);
});

test("suggest returns sorted completions", () => {
  const t = build();
  assert.deepEqual(t.suggest("car"), ["car", "card", "care", "careful"]);
  assert.deepEqual(t.suggest("ca", 3), ["car", "card", "care"]);
  assert.deepEqual(t.suggest("x"), []);
});

និង src/union-find.test.ts៖

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  UnionFind,
  countComponents,
  findRedundantEdge,
} from "./union-find.ts";

test("union merges groups and reports repeats", () => {
  const uf = new UnionFind(6);
  assert.equal(uf.union(0, 1), true);
  assert.equal(uf.union(1, 2), true);
  assert.equal(uf.union(0, 2), false);
  assert.equal(uf.connected(0, 2), true);
  assert.equal(uf.connected(0, 5), false);
  assert.equal(uf.count, 4);
});

test("countComponents", () => {
  assert.equal(countComponents(5, [[0, 1], [1, 2], [3, 4]]), 2);
  assert.equal(countComponents(6, [[0, 1], [1, 2], [3, 4]]), 3);
});

test("findRedundantEdge", () => {
  assert.deepEqual(findRedundantEdge([[1, 2], [1, 3], [2, 3]]), [2, 3]);
  assert.equal(findRedundantEdge([[1, 2], [2, 3]]), null);
});

ដំណើរការវា៖

npx tsx --test

test ទាំងអស់គួរតែឆ្លងកាត់។ ប្រសិនបើ test មួយបរាជ័យ សូមអានសារ៖ វាបង្ហាញតម្លៃរំពឹងទុក និងតម្លៃពិតប្រាកដនៅជាប់គ្នា។

12. សាកល្បងដោយខ្លួនឯង

1. លុបពី trie។ បន្ថែម method remove(word) ដែលដកសម្គាល់ពាក្យ។ បន្ទាប់មកធ្វើឲ្យប្រសើរឡើង៖ ក៏លុប node ដែលលែងនៅលើ path នៃពាក្យណាមួយដែរ។ ហេតុអ្វីអ្នកត្រូវប្រុងប្រយ័ត្នកុំលុប car នៅពេលលុប card ហើយកុំលុប card នៅពេលលុប car?
2. រាប់ពាក្យ។ បន្ថែម method countWithPrefix(prefix) ដែលត្រឡប់ចំនួនពាក្យដែលបានរក្សាទុកដែលចាប់ផ្តើមដោយ prefix។ ជំនួយ៖ រក្សាទុក counter ក្នុង node នីមួយៗដែលកើនឡើងរាល់ insert ដែលឆ្លងកាត់វា ហើយចម្លើយក្លាយជា O(L)។
3. Longest common prefix។ ដោយមាន ["flower", "flow", "flight"] ចម្លើយគឺ "fl"។ ដោះស្រាយដោយបញ្ចូលពាក្យទាំងអស់ក្នុង trie ហើយដើរចុះខណៈ node បច្ចុប្បន្នមាន child តែមួយ ហើយមិនមែនជាចុងពាក្យ។ (បុរាណក្នុងការសម្ភាសន៍។)
4. វចនានុក្រមពាក្យដែលមាន wildcard។ គាំទ្រ search("c.t") ដែល . ផ្គូផ្គងអក្សរមួយណាក៏បាន។ ជំនួយ៖ នៅពេលអ្នកឃើញ . សាកល្បងគ្រប់ child ដោយ recursion (ជំពូកទី 6)។
5. ទំហំនៃក្រុមធំបំផុត។ ពង្រីក UnionFind ជាមួយ array size ដើម្បីឲ្យ sizeOf(x) ត្រឡប់ចំនួនធាតុក្នុងក្រុមរបស់ x។ ធ្វើបច្ចុប្បន្នភាពវាក្នុង union។ សាកល្បងជាមួយធាតុ 6 និងការបញ្ចូលពីរបីដង។
6. បញ្ចូល account។ Account នីមួយៗមានឈ្មោះ និង email។ Account ពីរដែលមាន email រួមគ្នាជាកម្មសិទ្ធិរបស់មនុស្សតែមួយ។ ប្រើ union-find លើ index នៃ account ជាមួយ Map ពី email ទៅ index នៃ account ដំបូងដែលបានប្រើវា ដើម្បីដាក់ក្រុមពួកវា។ (រចនាប័ទ្មសម្ភាសន៍ កម្រិតមធ្យម។)

Trie ឆ្លើយសំណួរ prefix ដោយអនុញ្ញាតឲ្យពាក្យចែករំលែកការចាប់ផ្តើមរបស់ពួកវា។ Union-find ឆ្លើយ "តើទាំងនេះភ្ជាប់គ្នាទេ?" ដោយអនុញ្ញាតឲ្យក្រុមចែករំលែកតំណាងតែមួយ។ នៅជំពូកបន្ទាប់ Greedy និង Dynamic Programming យើងនឹងចាកចេញពី structure ហើយមើលវិធីពីរក្នុងការរចនា algorithm៖ តែងតែជ្រើសជម្រើសដែលមើលទៅល្អបំផុតនៅពេលនេះ និងចងចាំចម្លើយនៃបញ្ហាតូចៗ ដើម្បីកុំឲ្យដោះស្រាយពីរដង។