Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Xin chào mọi người! Mình là Loser1 từ Learning AI with Loser. Hôm nay chúng ta sẽ cùng nhau giải quyết một bài toán thú vị về đồ thị có hướng. Let’s make our path safe! 🎯
Chào các bạn, bạn có thể xem Đề bài và Giải pháp của mình trên LeetCode tại đây:
Có một đồ thị có hướng gồm n đỉnh, mỗi đỉnh được đánh số từ 0 đến n – 1. Đồ thị được biểu diễn bằng mảng 2D số nguyên graph
chỉ số 0, trong đó graph[i]
là mảng các đỉnh liền kề với đỉnh i, có nghĩa là có một cạnh từ đỉnh i đến các đỉnh trong graph[i]
.
Đỉnh được gọi là đỉnh kết thúc nếu không có cạnh đi ra khỏi đỉnh đó. Đỉnh an toàn là đỉnh mà mọi đường đi bắt đầu từ đỉnh đó đều dẫn đến một đỉnh kết thúc (hoặc đỉnh an toàn khác).
Trả về một mảng chứa tất cả các đỉnh an toàn của đồ thị. Kết quả phải được sắp xếp theo thứ tự tăng dần.
Ví dụ 1:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]] Output: [2,4,5,6] Giải thích: Đồ thị trên được biểu diễn như hình dưới đây. Các đỉnh 5 và 6 là đỉnh kết thúc vì không có cạnh nào đi ra khỏi các đỉnh này. Mọi đường đi bắt đầu từ các đỉnh 2, 4, 5, và 6 đều dẫn đến đỉnh 5 hoặc 6.
Ví dụ 2:
Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] Output: [4] Giải thích: Chỉ có đỉnh 4 là đỉnh kết thúc, và mọi đường đi bắt đầu từ đỉnh 4 đều dẫn đến chính đỉnh 4.
Ràng buộc:
n == graph.length
1 <= n <= 104
0 <= graph[i].length <= n
0 <= graph[i][j] <= n - 1
graph[i]
được sắp xếp theo thứ tự tăng dần.Cho một đồ thị có hướng n nodes (0 đến n-1). Một node được gọi là:
Nhiệm vụ: Tìm tất cả các safe nodes, sắp xếp theo thứ tự tăng dần.
Khi mới nhìn vào bài này, mình liên tưởng đến một mê cung với nhiều lối đi:
Đồ thị mẫu: Phân tích:
┌──────┐ 🔵: Safe node
0→1→2→5 │ 🔴: Unsafe node (có cycle)
↓ ↓ │ ⭕: Terminal node
3←0 │
↓ │ 2 → 5 → ∅ (Safe path)
4→5→∅ │ 4 → 5 → ∅ (Safe path)
Key Insights! 💡
Case 1: Terminal Case 2: Dẫn tới Terminal Case 3: Có cycle
5 → ∅ 2 → 5 → ∅ 0 → 1 → 2 → 3 → 0
✅ Safe! ✅ Safe! ❌ Unsafe!
Một node là unsafe nếu:
- Nằm trong một cycle
- HOẶC có đường đi đến một cycle
vis[node] = 0: Chưa visit
vis[node] = 1: Đang visit (trong stack)
vis[node] = 2: Đã visit xong (safe)
class Solution {
public:
bool dfs(int node, vector<vector<int>>& graph, vector<int>& vis) {
// Đang visit → Có cycle
if(vis[node] == 1) return false;
// Đã visit → Return trạng thái
if(vis[node] == 2) return true;
// Đánh dấu đang visit
vis[node] = 1;
// Check all neighbors
for(int next : graph[node]) {
if(!dfs(next, graph, vis)) return false;
}
// Đánh dấu safe
vis[node] = 2;
return true;
}
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> vis(n, 0);
vector<int> result;
// DFS từ mỗi node
for(int i = 0; i < n; i++) {
if(dfs(i, graph, vis)) {
result.push_back(i);
}
}
return result;
}
};
Input: graph = [[1,2], [2,3], [5], [0], [5], [], []]
Step 1: DFS từ node 0
- Visit path: 0 → 1 → 2 → 5
* vis[5] = 2 (terminal)
* vis[2] = 2 (dẫn tới terminal)
* vis[1] = 2 (dẫn tới safe)
* vis[0] = 2 (dẫn tới safe)
Visualization từng bước:
0(1) → 1(1) → 2(1) → 5(1)
0(1) → 1(1) → 2(1) → 5(2) ✅
0(1) → 1(1) → 2(2) ✅
0(1) → 1(2) ✅
0(2) ✅
Result: [2,4,5,6] (đã sort)
Chúc mọi người code vui! Hẹn gặp lại trong các bài Leetcode tiếp theo! 🚀
P/S: Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨
CODE EDITOR
#leetcode #leetcodedaily #algorithms #programming #learningwithlosers