Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

Daily Leetcode Challenge Day 15: 802. Find Eventual Safe States – Hành Trình An Toàn! 🚀

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àiGiải pháp của mình trên LeetCode tại đây:

802. Tìm các trạng thái an toàn cuối cùng

Medium
Đã giải

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

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.
  • Đồ thị có thể chứa các vòng lặp tự thân.
  • Số lượng cạnh trong đồ thị sẽ nằm trong phạm vi [1, 4 * 104].

Problem Statement

Cho một đồ thị có hướng n nodes (0 đến n-1). Một node được gọi là:

  • Terminal node: Không có cạnh đi ra
  • Safe node: Mọi đường đi từ node này đều dẫn đến terminal node

Nhiệm vụ: Tìm tất cả các safe nodes, sắp xếp theo thứ tự tăng dần.

First Thoughts & Intuition 🧠

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
0125   │              🔴: Unsafe node (có cycle)
  ↓ ↓     │              ⭕: Terminal node
  30
  ↓       │              25 → ∅  (Safe path)
  45→∅   │              45 → ∅  (Safe path)

Key Insights! 💡

  1. Nhận diện Safe Node:
   Case 1: Terminal     Case 2: Dẫn tới Terminal    Case 3: Có cycle
   5 → ∅               25 → ∅                   01230
   ✅ Safe!            ✅ Safe!                     ❌ Unsafe!
  1. Phân tích chu trình:
   Một node là unsafe nếu:
   - Nằm trong một cycle
   - HOẶC có đường đi đến một cycle

Approach

  1. DFS với 3 trạng thái:
   vis[node] = 0: Chưa visit
   vis[node] = 1: Đang visit (trong stack)
   vis[node] = 2: Đã visit xong (safe)
  1. Detect cycle:
  • Nếu gặp node đang visit → Có cycle
  • Nếu gặp node unsafe → Path unsafe
  • Nếu tất cả neighbors safe → Node safe
  1. Kết quả:
  • Thu thập các node có vis[node] = 2

Code Implementation

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

Example Walkthrough

Input: graph = [[1,2], [2,3], [5], [0], [5], [], []]

Step 1: DFS từ node 0
- Visit path: 0125
  * 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)

Complexity Analysis

  • Time: O(V + E) - V là số nodes, E là số edges
  • Space: O(V) - cho mảng visited và recursion stack

Tips & Tricks

  1. Dùng 3 states cho visited giúp detect cycle hiệu quả
  2. DFS là perfect choice cho bài toán path finding
  3. Terminal nodes luôn là safe nodes

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: 50

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?
Bei der riester rente kannst du zum beispiel deine beiträge als. Heavy equipment transport middlesex nj logi transports fast & reliable heavy equipment transport & transport services. Free & easy backlink link building.