Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Xin chào các bạn yêu quý của Loser1! Hôm nay chúng ta sẽ cùng khám phá bài toán về lịch học siêu thú vị – nơi mà các môn học được kết nối với nhau như một mạng lưới kiến thức! Let’s discover! 🎓
Có tổng cộng numCourses
khóa học mà bạn phải tham gia, được đánh số từ 0
đến numCourses - 1
. Bạn được cung cấp một mảng prerequisites
trong đó prerequisites[i] = [ai, bi]
chỉ ra rằng bạn phải tham gia khóa học ai
trước nếu bạn muốn tham gia khóa học bi
.
Ví dụ, cặp [0, 1]
chỉ ra rằng bạn phải tham gia khóa học 0
trước khi bạn có thể tham gia khóa học 1
.
Các điều kiện tiên quyết cũng có thể là gián tiếp. Nếu khóa học a
là điều kiện tiên quyết của khóa học b
, và khóa học b
là điều kiện tiên quyết của khóa học c
, thì khóa học a
là điều kiện tiên quyết của khóa học c
.
Bạn cũng được cung cấp một mảng queries
trong đó queries[j] = [uj, vj]
. Đối với truy vấn thứ j
, bạn cần trả lời xem khóa học uj
có phải là điều kiện tiên quyết của khóa học vj
hay không.
Trả về một mảng boolean answer
, trong đó answer[j]
là câu trả lời cho truy vấn thứ j
.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]] Output: [false,true] Explanation: Cặp [1, 0] chỉ ra rằng bạn phải tham gia khóa học 1 trước khi bạn có thể tham gia khóa học 0. Khóa học 0 không phải là điều kiện tiên quyết của khóa học 1, nhưng ngược lại là đúng.
Example 2:
Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]] Output: [false,false] Explanation: Không có điều kiện tiên quyết nào, và mỗi khóa học là độc lập.
Example 3:
Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]] Output: [true,true] Explanation: Khóa học 1 là điều kiện tiên quyết của khóa học 0 và khóa học 2.
Constraints:
2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= numCourses - 1
ai != bi
[ai, bi]
là duy nhất.1 <= queries.length <= 104
0 <= ui, vi <= numCourses - 1
ui != vi
Khi nhìn vào bài này, mình liên tưởng ngay đến việc lập kế hoạch học tập tại trường:
Giống như việc:
- Bạn phải học Toán trước khi học Giải Tích
- Học Lý trước khi học Điện
- Nếu A→B và B→C thì A→C (gián tiếp)
Ví dụ: prerequisites = [[1,2], [1,0], [2,0]]
Visualize như một sơ đồ:
1 ━━━━━━━┓
┃
▼
2 ━━━━━━━▶ 0
Giải thích:
💡 1 → 2: Học 1 trước 2
💡 1 → 0: Học 1 trước 0
💡 2 → 0: Học 2 trước 0
Pattern 1: Direct Path Pattern 2: Indirect Path
A → B A → B → C
(Trực tiếp) (A là prerequisite của C)
Pattern 3: No Path Pattern 4: Multiple Paths
A B A → B → D
(Độc lập) ↘ ↗
C
// Create adjacency list
vector<vector<int>> adj(numCourses);
for(auto& pre : prerequisites) {
adj[pre[0]].push_back(pre[1]);
}
// Visualize:
// prerequisites = [[1,2], [1,0], [2,0]]
// adj[1] = [2,0] // Khóa 1 dẫn đến 2 và 0
// adj[2] = [0] // Khóa 2 dẫn đến 0
// adj[0] = [] // Khóa 0 không dẫn đến đâu
void dfs(int node, vector<bool>& visited,
vector<vector<int>>& adj,
vector<vector<bool>>& reachable) {
visited[node] = true;
// Explore all neighbors
for(int next : adj[node]) {
// If not visited, explore deeper
if(!visited[next]) {
dfs(next, visited, adj, reachable);
}
// Mark direct connection
reachable[node][next] = true;
// Mark indirect connections
for(int k = 0; k < reachable.size(); k++) {
if(reachable[next][k]) {
reachable[node][k] = true;
}
}
}
}
class Solution {
public:
vector<bool> checkIfPrerequisite(int numCourses,
vector<vector<int>>& prerequisites,
vector<vector<int>>& queries) {
// Initialize structures
vector<vector<int>> adj(numCourses);
vector<vector<bool>> reachable(numCourses,
vector<bool>(numCourses, false));
// Build graph
for(auto& pre : prerequisites) {
adj[pre[0]].push_back(pre[1]);
}
// Run DFS for each course
for(int i = 0; i < numCourses; i++) {
vector<bool> visited(numCourses, false);
dfs(i, visited, adj, reachable);
}
// Process queries
vector<bool> result;
for(auto& q : queries) {
result.push_back(reachable[q[0]][q[1]]);
}
return result;
}
};
Let's analyze: numCourses = 3, prerequisites = [[1,2], [1,0], [2,0]]
Initial State:
1 → Empty
2 → Empty Transform to 1 → [2,0]
0 → Empty 2 → [0]
0 → []
Start DFS from course 1:
1. Visit 1
└── Visit 2
└── Visit 0
└── Visit 0 (already reached)
Reachability Matrix Update:
0 1 2
0 F F F
1 T F T ← Course 1 can reach 0 and 2
2 T F F ← Course 2 can reach 0
Query [1,0]:
Check reachable[1][0] = true
→ Course 1 is prerequisite of 0
Query [1,2]:
Check reachable[1][2] = true
→ Course 1 is prerequisite of 2
Draw the graph first!
⭕ → ⭕
↘ ↓
⭕
Case 1: No prerequisites
[] → All queries false
Case 2: Direct path
[1,0] → Query [1,0] true
Case 3: Indirect path
[1,2], [2,0] → Query [1,0] true
- Use adjacency list instead of matrix
- Cache results in reachability matrix
- Early termination when possible
Time: O(N * (N + E))
└── N courses
└── E prerequisites
└── DFS for each course
Space: O(N^2)
└── Reachability matrix
└── Adjacency list
└── Visited array
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