399. Evaluate Division
Tags:
Medium
Skills:
Graph
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu bạn tính giá trị của các phép chia giữa các biến dựa trên một số phương trình cho trước
- Bạn có danh sách các phương trình dạng A / B = k (với A, B là biến, k là số thực dương)
- Bạn cần trả lời các truy vấn dạng
C / D = ?dựa trên các phương trình đã cho. - Nếu không thể xác định giá trị, trả về
-1.0
Approach
Bài toán này có thể được mô hình hóa thành đồ thị có trọng số:
- Mỗi biến là một đỉnh (node)
- Mỗi phương trình A / B = k là một cạnh có hướng từ A đến B với trọng số k, và ngược lại từ B đến A với trọng số 1/k
- Để trả lời truy vấn C / D, bạn cần tìm đường đi từ C đến D và nhân các trọng số trên đường đi đó
Có 2 cách phổ biến
- DFS/ BFS trên đồ thị: Duyệt từ C đến D, tích lũy tích các trọng số
- Union-Find có trọng số: Dùng cấu trúc Disjoint set để quản lý nhóm biên liên thông và lưu tỷ lệ giữa các biến với gốc nhóm
💡
Solution - DFS
Các bước DFS
- Xây dựng đồ thị từ các phương trình
- Với mỗi truy vấn, dùng DFS để tìm đường đi từ biến đầu đến biến cuối, tích lũy các trọng số
- Nếu không tìm được đường đi, trả về -1.0
typescripttypescript
1function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
2 const graph: Record<string, [string, number][]> = {};
3 for (let i = 0; i < equations.length; i++) {
4 const [a, b] = equations[i];
5 const val = values[i];
6
7 if (!graph[a]) graph[a] = [];
8 if (!graph[b]) graph[b] = [];
9 graph[a].push([b, val]);
10 graph[b].push([a, 1 / val]);
11 }
12
13 function dfs(curr: string, target: string, visisted: Set<string>): number {
14 if (!(curr in graph) || !(target in graph)) return -1.0;
15 if (curr === target) return 1.0;
16 visisted.add(curr);
17 for (const [neighbor, weight] of graph[curr]) {
18 if (!visisted.has(neighbor)) {
19 const res = dfs(neighbor, target, visisted);
20 if (res !== -1.0) {
21 return res * weight
22 }
23 }
24 }
25
26 return -1.0
27 }
28
29 const res: number[] = [];
30 for (const [start, end] of queries) {
31 const visisted = new Set<string>();
32 res.push(dfs(start, end, visisted));
33 }
34 return res;
35};💡
Approach- Union Find
typescripttypescript
1class UnionFind {
2 parent: number[];
3 rank: number[];
4 weight: number[];
5 constructor(size: number) {
6 this.parent = Array.from({ length: size }, (_, i) => i)
7 this.rank = Array(size).fill(0);;
8 this.weight = Array(size).fill(1.0);;
9 }
10 find(node: number): number {
11 if (this.parent[node] !== node) {
12 const ori_parent = this.parent[node]
13 this.parent[node] = this.find(this.parent[node])
14 this.weight[node] = this.weight[node] * this.weight[ori_parent]
15 }
16 return this.parent[node];
17 }
18
19 union(nodeA: number, nodeB: number, value: number): boolean {
20 const rootA = this.find(nodeA);
21 const rootB = this.find(nodeB);
22 if (rootA === rootB) return false;
23 if (this.rank[rootA] > this.rank[rootB]) {
24 this.parent[rootB] = rootA;
25 this.weight[rootB] = this.weight[nodeA] / (this.weight[nodeB] * value)
26 } else {
27 this.parent[rootA] = rootB;
28 this.weight[rootA] = (this.weight[nodeB] * value) / this.weight[nodeA]
29 if (this.rank[rootA] === this.rank[rootB]) {
30 this.rank[rootB]++
31 }
32 }
33
34 return true
35 }
36
37 isConnected(nodeA: number, nodeB: number): number {
38 if (this.find(nodeA) !== this.find(nodeB)) return -1.0
39 return this.weight[nodeA] / this.weight[nodeB]
40 }
41}
42
43function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
44 const var_id: Map<string, number> = new Map();
45 let id = 0;
46 for (const [a, b] of equations) {
47 if (!var_id.has(a)) var_id.set(a, id++);
48 if (!var_id.has(b)) var_id.set(b, id++)
49 }
50
51 const uf = new UnionFind(id);
52 for (let i = 0; i < equations.length; i++) {
53 const [a, b] = equations[i];
54 uf.union(var_id.get(a), var_id.get(b), values[i])
55 }
56
57 const res: number[] = [];
58 for (const [a, b] of queries) {
59 if (!var_id.has(a) || !var_id.has(b)) {
60 res.push(-1.0)
61 } else {
62 res.push(uf.isConnected(var_id.get(a), var_id.get(b)))
63 }
64 }
65
66 return res;
67};💡
Tóm tắt
- Weight: mỗi node lưu tỷ số từ node đó đến parent của nó
- Sau mỗi lần union, weight[nodeA] sẽ là tỷ số từ nodeA → root của nhóm nodeA
- weight[nodeB] sẽ là tỷ số từ nodeA → root của nhóm nodeB
- Khi bạn cần tính tỷ số giữa hai biến cùng nhóm (VD:
a/c) bạn chỉ cần lấy: - find: Khi path compression, weight được cập nhật để đảm bảo đúng tỷ số
- union: Khi nối hai root, cập nhật weight để giữ đúng tỷ số giữa các node
- isConnected: Nếu hai node cùng root, return về tỷ số của chúng, nếu không return -1
💡
Ý nghĩa của mảng weight
weight[a] / weight[c] (với điều kiện cả hai cùng trỏ về một root chung).
💡
Dry run
1. "Root" trong Union-Find là gì?
- Root là đại diện của một nhóm các biến liên thông với nhau (có thể chuyển đổi qua lại bằng các phép chia/multiplication).
- Mỗi biến đều trỏ (qua parent) về một biến gốc (root) của nhóm của nó.
- Không phải lúc nào root cũng là 'a'; root có thể là bất kỳ biến nào tuỳ vào thứ tự union.
2. Ví dụ cụ thể:
Giả sử bạn có các phép chia:
a / b = 2.0b / c = 3.0c / d = 4.0
Sau khi union lần lượt, có thể cây sẽ như sau (giả sử luôn gắn node bên phải vào node bên trái):
typescripttypescript
1a
2|
3b
4|
5c
6|
7d
8- parent: [a, a, b, c] (a là root của b, b là root của c, c là root của d)
- weight: [1.0, 2.0, 3.0, 4.0]
- weight= x / parent[x]
3. Tính các phép chia
a. Để tính a / d:
- Tìm root của a và d (cùng là a)
- Tính weight từ d lên root:
- d / c = 4.0
- c / b = 3.0
- b / a = 2.0
- Vậy: d / a = 4.0 * 3.0 * 2.0 = 24.0
- a / d = 1 / 24.0 ≈ 0.0417
b. Để tính b / c:
- b / c = (b / a) / (c / a) = (2.0) / (2.0 * 3.0) = 2.0 / 6.0 = 1/3
c. Để tính a / b:
- a / b = 1 / 2.0 = 0.5
- Tại sao phải tìm root?
- Để đảm bảo hai biến có cùng nhóm (liên thông), tức là có thể chuyển đôi qua lại được
- Để tính đúng tỷ số, bạn cần biết weight của mỗi biến so với root, rồi lấy tỷ số của hai biến đó
5. Kết luận
Root không nhất thiết là 'a'. Root là đại diện của nhóm, có thể là bất kỳ biến nào.
Bạn cần tìm root để kiểm tra hai biến có liên thông không (nếu không, phép chia không xác định).
Bạn cần weight từ biến đến root để tính đúng mọi phép chia giữa các biến trong cùng nhóm.
💡
Tại sao lại có
this.weight[node] *= this.weight[ori_parent];this.weight[node]là tỷ số giữanode và parent[node](tức là node / parent[node])this.weight[ori_parent]: là tỷ số giữaori_parentparent[ori_parent](cha mới sau khi nén đường).\- Khi thực hiện path compression,
parent[node]sẽ được cập nhật thànhparent[ori_parent](gốc cuối cùng) - Để duy trì đúng tỷ số giữa node và gốc mới, cần nhân tỷ số hiện tại với tỷ số cha cũ lên gốc mới
Minh họa bằng ví dụ
Giả sử ta có chuỗi liên kết như sau:
typescripttypescript
1node → ori_parent → root- weight[node] = node / ori_parent
- weight[ori_parent] = ori_parent / root
Sau khi path compression, node sẽ trỏ trực tiếp về root.
Ta cần cập nhật:
typescripttypescript
1weight[node] = node / root = (node / ori_parent) * (ori_parent / root)
2 = weight[node] * weight[ori_parent]=> Đó chính là lý do phải nhân thêm this.weight[ori_parent].
Tóm lại
- Mục đích: Đảm bảo sau khi path compression, tỷ số từ node đến gốc mới (root) là chính xác.
- Nếu không có dòng này: Các phép tính tỷ số giữa các node sẽ bị sai sau khi path compression, dẫn đến kết quả sai cho các truy vấn.
Minh họa cụ thể
Giả sử bạn có:
a / b = 2.0b / c = 3.0
Sau khi union, cây có thể như sau:
typescripttypescript
1a -> b -> c- weight[a] = 2.0 (a / b)
- weight[b] = 3.0 (b / c)
Nếu bạn thực hiện find(a), bạn sẽ path compression để a trỏ trực tiếp về c (gốc của nhóm).
Khi đó, bạn cần cập nhật:
typescripttypescript
1weight[a] = a / c = (a / b) * (b / c) = 2.0 * 3.0 = 6.0Điều này chính là:
typescripttypescript
1this.weight[a] *= this.weight[b]; // a / c = (a / b) * (b / c)💡
Tại sao lại có
this.weight[rootB] = this.weight[nodeA] / (value * this.weight[nodeB])là để cập nhật tỷ số từ rootB đến rootA sau khi union, đảm bảo rằng mọi phép chia giữa các node đều đúng với các phương trình đã cho.
Bạn biết:
nodeA / rootA = weight[nodeA]nodeB / rootB = weight[nodeB]nodeA / nodeB = value(theo phương trình đầu vào)
Bạn cần tìm weight[rootB] sao cho:
typescripttypescript
1(rootB / rootA) = weight[rootB]Ta có:
typescripttypescript
1nodeA / nodeB = value
2=> (nodeA / rootA) * (rootA / rootB) * (rootB / nodeB) = value
3=> (weight[nodeA]) * (1 / weight[rootB]) * (1 / weight[nodeB]) = value
4=> weight[nodeA] / (weight[rootB] * weight[nodeB]) = value
5=> weight[rootB] = weight[nodeA] / (value * weight[nodeB])💡
Tại sao lại có đoạn này?
typescripttypescript
1 const var_id: Map<string, number> = new Map();
2 let id= 0;
3 for(const [a, b] of equations) {
4 if(!var_id.has(a)) var_id.set(a, id++);
5 if(!var_id.has(b)) var_id.set(b, id++);
6 }- var_id: là một Map dùng để ánh xạ mỗi biến tên (string) sang một số nguyên duy nhất (index).
- id: là biến đếm, mỗi khi gặp biến mới sẽ tăng lên 1.
Cụ thể:
- Khi lặp qua từng phương trình
[a, b], nếu biếnachưa từng xuất hiện thì gán cho nó một index mới, tương tự vớib. - Sau vòng lặp, tất cả các biến đều đã có chỉ số nguyên duy nhất.
Ví dụ minh họa
Giả sử bạn có equations = [["a","b"],["b","c"]]:
- Lần đầu gặp "a" → var_id.set("a", 0), id = 1
- Lần đầu gặp "b" → var_id.set("b", 1), id = 2
- "b" đã có, bỏ qua
- Lần đầu gặp "c" → var_id.set("c", 2), id = 3
Sau đoạn code này:
- "a" → 0
- "b" → 1
- "c" → 2
Kết luận
Đoạn code này là bước chuyển đổi cần thiết để bạn có thể áp dụng Union-find cho các biến dạng chuỗi trong bài Evaluate Division. Nếu không có nó, bạn không thể dùng Union-Find chuẩn để giải bài này
💡
Deep dive
typescripttypescript
1if(this.rank[rootA] > this.rank[rootB) {
2 this.parent[rootB] = rootA;
3 this.weight[rootB] = this.weight[nodeA] / (value * this.weight[nodeB])
4 } else {
5 this.parent[rootA] = rootB;
6 this.weight[rootA] = (value * this.weight[nodeB]) / this.weight[nodeA];
7 if (this.rank[rootA] === this.rank[rootB]) {
8 this.rank[rootB]++;
9 }
10 }
11Giả sử trạng thái trước khi union
nodeAthuộc nhóm gốcrootAnodeBthuộc nhóm gốcrootBnodeA / rootA = weight[nodeA]nodeB / rootB = weight[nodeB]- Bạn biết:
nodeA / nodeB = value
typescripttypescript
1nodeA / rootA = weight[nodeA]
2nodeB / rootB = weight[nodeB]
3nodeA / nodeB = value- Union-Find chuẩn (không trọng số)
- Gắn cây có rank nhỏ hơn vào cây có rank lớn hơn để giữ cây thấp nhất có thể (giúp find nhanh)
- Nếu hai cây bằng rank, gắn một cây vào cây kia và tăng rank
- Union-Find có trọng số (Evaluation Division)
- Gắn rootB vào rootA (rootA làm cha của rootB).
- Cập nhật weight[rootB] để đảm bảo:
- Công thức:
- Lý do:
- Gắn rootA vào rootB (rootB làm cha của rootA).
- Cập nhật weight[rootA] để đảm bảo:
- Công thức:
- Lý do:
- Gắn rootB vào rootA (hoặc ngược lại, tuỳ bạn chọn).
- Cập nhật weight như ở nhánh a.
- Tăng rank[rootA] vì cây mới cao hơn.
Khi gộp hai cây lại, bạn thường
Ngoài việc gắn parent, bạn còn phải cập nhật weight để đảm bảo mọi phép chia vẫn đúng
Cụ thể từng nhánh:
a. Nếu rank[rootA] > rank[rootB]
typescripttypescript
1this.parent[rootB] = rootA;
2this.weight[rootB] = this.weight[nodeA] / (value * this.weight[nodeB]);rootB / rootA = ?
rootB / rootA = weight[nodeA] / (value * weight[nodeB])
Đảm bảo mọi phép chia giữa hai nhóm đúng với phương trình nodeA / nodeB = value (như các giải thích ở trên).
b. Nếu rank[rootA] < rank[rootB]
typescripttypescript
1this.parent[rootA] = rootB;
2this.weight[rootA] = (value * this.weight[nodeB]) / this.weight[nodeA];rootA / rootB = ?
rootA / rootB = (value * weight[nodeB]) / weight[nodeA]
Tương tự, đảm bảo mọi phép chia giữa hai nhóm đúng với phương trình đã cho.
c. Nếu rank bằng nhau
typescripttypescript
1this.parent[rootB] = rootA;
2this.weight[rootB] = this.weight[nodeA] / (value * this.weight[nodeB]);
3this.rank[rootA]++;