Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

Daily Leetcode Challenge Day 18: 1462. Course Schedule IV – Học Sao Cho Đúng Thứ Tự! 📚

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! 🎓

1462. Course Schedule IV

Medium
Đã giải

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 1

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.
Example 3

Constraints:

  • 2 <= numCourses <= 100
  • 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
  • prerequisites[i].length == 2
  • 0 <= ai, bi <= numCourses - 1
  • ai != bi
  • Tất cả các cặp [ai, bi] là duy nhất.
  • Đồ thị điều kiện tiên quyết không có chu trình.
  • 1 <= queries.length <= 104
  • 0 <= ui, vi <= numCourses - 1
  • ui != vi

First Thoughts & Intuition 🧠

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:

1. Tưởng tượng Lịch Học 📅

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)

2. Phân Tích Quan Hệ 🔍

Ví dụ: prerequisites = [[1,2], [1,0], [2,0]]

Visualize như một sơ đồ:
1 ━━━━━━━┓


2 ━━━━━━━▶ 0

Giải thích:
💡 12: Học 1 trước 2
💡 10: Học 1 trước 0
💡 20: Học 2 trước 0

3. Key Insights 🎯

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

Super Detailed Approach 📝

1. Graph Building 🏗️

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

2. DFS Implementation 🚀

C++
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;
            }
        }
    }
}

3. Main Solution 🎨

C++
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;
    }
};

Detailed Example Walkthrough 🎮

Let's analyze: numCourses = 3, prerequisites = [[1,2], [1,0], [2,0]]

Step 1: Graph Building 📊

Initial State:
1 → Empty
2 → Empty    Transform to    1 → [2,0]
0 → Empty                    2 → [0]
                            0 → []

Step 2: DFS Process 🔄

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

Step 3: Query Processing ✨

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

Advanced Tips & Tricks 💡

  1. Visualization Tips:
Draw the graph first!
    ⭕ → ⭕
     ↘  ↓
  1. Edge Cases:
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
  1. Performance Tips:
- Use adjacency list instead of matrix
- Cache results in reachability matrix
- Early termination when possible

Complexity Analysis 📊

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

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Heavy equipment transport new york ny logi transports fast & reliable heavy equipment transport & transport services.