3310. Remove Methods From Project

題目 / Problem

中文：你在維護一個專案，裡面有 n 個方法（method），編號 0 到 n-1。給你整數 n、k，以及一個二維陣列 invocations，其中 invocations[i] = [a, b] 表示「方法 a 會呼叫方法 b」。方法 k 有已知的 bug。方法 k 本身，以及任何被它「直接或間接」呼叫到的方法，都算作可疑（suspicious），我們想把它們移除。但有一條規則：只有當群組外部沒有任何方法呼叫群組內部的方法時，這個群組才能被移除。請回傳移除所有可疑方法後剩下的方法（順序不限）。如果無法把所有可疑方法都移除，那就一個都不移除，回傳全部方法。

English: You maintain a project with n methods numbered 0 to n-1. Given n, k, and a 2D array invocations where invocations[i] = [a, b] means "method a invokes method b". Method k has a bug. Method k, plus every method it can reach directly or indirectly, is suspicious and we want to remove them. A group can only be removed if no method outside the group invokes any method inside it. Return the remaining methods after removal (any order). If we cannot remove all suspicious methods, remove none and return every method.

Constraints / 限制 - 1 <= n <= 10^5 - 0 <= k <= n - 1 - 0 <= invocations.length <= 2 * 10^5 - invocations[i] = [a, b], 0 <= a, b <= n-1, a != b, no duplicate pairs.

Worked example / 範例 n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]] → Output [3,4]. 從方法 0 出發能到達 0、1、2，這三個是可疑的；沒有其他方法呼叫它們，所以可以安全移除，剩下 [3, 4]。

名詞解釋 / Glossary

有向圖 / directed graph：由節點（這裡是方法）和有方向的邊組成。邊 a → b 表示「a 呼叫 b」，方向不能反過來。
鄰接表 / adjacency list：儲存圖的常用方式。對每個節點記錄「它指向哪些節點」的清單。比用 n×n 的矩陣省空間，因為只存實際存在的邊。
DFS（深度優先搜尋）/ Depth-First Search：一種走訪圖的方法，從某個節點出發，沿著邊一路走到底再回頭。這裡用來找出「從 k 能到達的所有節點」。
BFS（廣度優先搜尋）/ Breadth-First Search：另一種走訪方式，一層一層往外擴散。對「找可達集合」這個目的，DFS 和 BFS 效果相同。
可達性 / reachability：從一個節點沿著有向邊能不能走到另一個節點。可疑集合就是「從 k 可達的所有節點」。
visited 標記陣列 / visited array：一個布林陣列，記錄每個節點是否已經走訪過，避免同一個節點被重複處理、也避免在有環（cycle）的圖裡無限迴圈。
迭代式 DFS / iterative DFS with an explicit stack：用自己維護的堆疊（陣列）代替遞迴函式呼叫。因為 n 可達 10^5，遞迴太深可能造成 stack overflow（堆疊溢位），所以改用迴圈比較安全。

思路

暴力的想法是：先想辦法找出所有可疑方法，然後對每個可疑方法檢查「有沒有非可疑的方法呼叫它」。但真正的關鍵有兩步。第一步是「找出可疑集合」：可疑的定義是「k 以及 k 直接或間接呼叫到的所有方法」，這其實就是在有向圖上，從 k 出發能到達的所有節點。我們建一個鄰接表（a → b），然後從 k 做一次 DFS 或 BFS，把走到的每個節點都在 suspicious 陣列裡標記為 true。這一步只會走過每條邊一次，很有效率。第二步是判斷「能不能移除」：規則說「群組外部不能呼叫群組內部」。所以我們掃過每一條邊 [a, b]，只要出現「a 不可疑、但 b 可疑」的情況，就代表有一個外部方法在呼叫可疑群組，於是整個群組都不能移除——這時直接回傳全部 0..n-1。如果掃完所有邊都沒有這種違規，就可以安全移除，回傳所有「不可疑」的方法。為什麼只要檢查邊就夠？因為「外部呼叫內部」一定表現為某條邊的起點在外、終點在內，掃邊就能完整涵蓋所有呼叫關係。用 visited 陣列可以避免圖中有環時無限迴圈。

The brute-force instinct is to find the suspicious set and then, for each suspicious method, check whether any non-suspicious method calls it. But the clean solution has just two steps. Step one, build the suspicious set: "suspicious" means k plus everything k reaches directly or indirectly, which is exactly the set of nodes reachable from k in the directed graph. Build an adjacency list (a → b), run a single DFS/BFS from k, and mark every visited node as suspicious. This touches each edge once. Step two, decide if removal is legal: the rule forbids any outside method calling into the group. So scan every edge [a, b]; if we ever see a not-suspicious but b suspicious, that's an outside caller reaching inside, so nothing can be removed — return all of 0..n-1. If no edge violates this, removal is safe, so return every non-suspicious method. Scanning edges suffices because "outside calls inside" always shows up as an edge whose tail is outside and head is inside. A visited array prevents infinite loops when the graph contains cycles.

逐步走查 / Walkthrough

用範例二 / Using Example 2: n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]].

建鄰接表 / Build adjacency list（a → b）： - 0 → [2, 1], 1 → [2], 3 → [4]（2 和 4 沒有出邊 / no outgoing edges）

DFS from k = 0，用堆疊 stack，suspicious 全部初始為 false：

步驟 Step	Stack（處理前）	彈出 Pop	標記 Mark suspicious	推入鄰居 Push neighbors
1	`[0]`	0	suspicious[0]=T	push 2, push 1
2	`[2, 1]`	1	suspicious[1]=T	push 2
3	`[2, 2]`	2	suspicious[2]=T	(無出邊 none)
4	`[2]`	2	已標記，跳過 already T, skip	—
5	`[]`	—	結束 done	—

結果 / Result：suspicious = [T, T, T, F, F] → 可疑節點是 0, 1, 2。

掃邊檢查外部呼叫 / Scan edges for outside→inside： - [1,2]：a=1 可疑 → 不算違規 / a suspicious, ok - [0,2]：a=0 可疑 → ok - [0,1]：a=0 可疑 → ok - [3,4]：a=3 不可疑，b=4 也不可疑 → ok

沒有任何違規 / No violation found → 可以移除可疑節點 / removal allowed.

收集結果 / Collect answer：所有 suspicious[i] == false 的節點 → i = 3, 4 → 輸出 [3, 4]。✅

Solution — C

// 演算法 / Algorithm:
// 1) 建鄰接表，從 k 做迭代式 DFS，標記所有可達（=可疑）節點。
//    Build adjacency list, iterative DFS from k, mark all reachable (=suspicious) nodes.
// 2) 掃每條邊：若有「非可疑 a 呼叫可疑 b」，則無法移除，回傳全部節點。
//    Scan edges: if any non-suspicious a calls suspicious b, removal fails -> return all.
// 3) 否則回傳所有非可疑節點。 Otherwise return every non-suspicious node.

#include <stdlib.h>   // malloc / calloc / free / realloc

int* remainingMethods(int n, int k, int** invocations, int invocationsSize,
                      int* invocationsColSize, int* returnSize) {
    // head[v] 存節點 v 的第一條邊的索引；-1 代表沒有邊（鏈式前向星）
    // head[v] = index of v's first edge; -1 means no edge (a linked adjacency list)
    int* head = (int*)malloc(sizeof(int) * n);          // 每個節點一個表頭 / one head per node
    for (int i = 0; i < n; i++) head[i] = -1;           // 初始化為 -1 / init to "no edge"

    // to[] 存邊的終點，nxt[] 存「同一起點的下一條邊」的索引，形成鏈結串列
    // to[] = edge's destination; nxt[] = index of next edge from same source (linked list)
    int m = invocationsSize;                            // 邊的數量 / number of edges
    int* to  = (int*)malloc(sizeof(int) * (m > 0 ? m : 1));  // 避免 malloc(0) / avoid malloc(0)
    int* nxt = (int*)malloc(sizeof(int) * (m > 0 ? m : 1));

    for (int e = 0; e < m; e++) {                       // 逐條邊加入鄰接表 / add each edge
        int a = invocations[e][0];                      // 起點 a / source a
        int b = invocations[e][1];                      // 終點 b / destination b
        to[e]  = b;                                     // 這條邊指向 b / this edge points to b
        nxt[e] = head[a];                               // 接到 a 原本的鏈頭 / link to a's old head
        head[a] = e;                                    // 新的鏈頭是 e / a's new head is edge e
    }

    // suspicious[v]：v 是否可疑（從 k 可達）。calloc 會把記憶體全設為 0(=false)
    // suspicious[v]: is v reachable from k? calloc zero-fills memory (0 = false)
    char* suspicious = (char*)calloc(n, sizeof(char));

    // 用陣列當作明確的堆疊做迭代式 DFS，避免遞迴太深導致 stack overflow
    // Use an array as an explicit stack for iterative DFS (avoids deep-recursion overflow)
    int* stack = (int*)malloc(sizeof(int) * n);
    int top = 0;                                        // top 指向堆疊下一個空位 / next free slot
    stack[top++] = k;                                   // 把起點 k 推入堆疊 / push start node k
    suspicious[k] = 1;                                  // k 本身就是可疑的 / k itself is suspicious

    while (top > 0) {                                   // 堆疊還有東西就繼續 / while stack not empty
        int u = stack[--top];                           // 彈出一個節點 u / pop a node u
        for (int e = head[u]; e != -1; e = nxt[e]) {    // 走過 u 的每條邊 / iterate u's edges
            int v = to[e];                              // 這條邊的終點 v / edge destination v
            if (!suspicious[v]) {                        // v 還沒被標記過才處理 / only if unvisited
                suspicious[v] = 1;                       // 標記 v 為可疑 / mark v suspicious
                stack[top++] = v;                        // 推入堆疊稍後展開 / push v to expand later
            }
        }
    }

    // 檢查是否有「外部呼叫內部」：非可疑的 a 呼叫可疑的 b
    // Check for any outside->inside call: non-suspicious a invoking suspicious b
    int canRemove = 1;                                  // 先假設可以移除 / assume removable
    for (int e = 0; e < m; e++) {
        int a = invocations[e][0];
        int b = invocations[e][1];
        if (!suspicious[a] && suspicious[b]) {           // a 在外、b 在內 = 違規 / outside calls inside
            canRemove = 0;                               // 不能移除任何東西 / cannot remove anything
            break;                                       // 找到一個就夠了 / one is enough, stop
        }
    }

    // 配置結果陣列，最多 n 個元素 / allocate result array, at most n elements
    int* ans = (int*)malloc(sizeof(int) * n);
    int cnt = 0;                                        // 已放入結果的數量 / count written so far

    if (canRemove) {                                    // 可以移除 -> 只留非可疑節點 / keep non-suspicious
        for (int i = 0; i < n; i++)
            if (!suspicious[i]) ans[cnt++] = i;
    } else {                                            // 不能移除 -> 全部保留 / keep everything
        for (int i = 0; i < n; i++)
            ans[cnt++] = i;
    }

    *returnSize = cnt;                                  // 透過指標回傳陣列長度 / report length via pointer

    free(head); free(to); free(nxt);                    // 釋放暫時記憶體，避免 memory leak
    free(suspicious); free(stack);                      // free temporary memory to avoid leaks
    return ans;                                         // 回傳結果陣列 / return the answer array
}

Solution — C++

// 演算法 / Algorithm:
// 1) 用 vector 建鄰接表，從 k 做迭代式 DFS，標記所有可疑（可達）節點。
//    Build adjacency list with vectors, iterative DFS from k, mark suspicious (reachable) nodes.
// 2) 掃每條邊，若非可疑 a 呼叫可疑 b -> 無法移除，回傳全部。
//    Scan edges; if non-suspicious a calls suspicious b -> cannot remove, return all.
// 3) 否則回傳所有非可疑節點。 Otherwise return every non-suspicious node.

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
        // adj[a] 是一個 vector，存 a 直接呼叫的所有節點 / adj[a] = list of nodes a calls directly
        vector<vector<int>> adj(n);                     // n 個空 vector / n empty adjacency lists
        for (auto& e : invocations)                     // range-for：逐條邊 / iterate each edge
            adj[e[0]].push_back(e[1]);                  // 在 a 的清單尾端加上 b / append b to a's list

        // suspicious[v]：v 是否從 k 可達 / whether v is reachable from k
        vector<char> suspicious(n, 0);                  // 用 char 當布林，初始全 0 / bool-like, all 0

        // 迭代式 DFS，用 vector 當堆疊，避免遞迴太深 / iterative DFS with a vector as an explicit stack
        vector<int> stk;                                // stk 就是我們的堆疊 / stk is our stack
        stk.push_back(k);                               // 推入起點 / push start node
        suspicious[k] = 1;                              // k 本身可疑 / k is suspicious
        while (!stk.empty()) {                          // 堆疊非空就繼續 / while stack not empty
            int u = stk.back(); stk.pop_back();         // 取出並移除頂端節點 / pop top node
            for (int v : adj[u]) {                      // 走過 u 呼叫的每個節點 / for each callee v
                if (!suspicious[v]) {                    // 只處理沒標記過的 / only unvisited
                    suspicious[v] = 1;                   // 標記可疑 / mark suspicious
                    stk.push_back(v);                    // 推入稍後展開 / push to expand later
                }
            }
        }

        // 檢查有沒有「外部呼叫內部」/ check for any outside->inside call
        bool canRemove = true;                          // 先假設可以移除 / assume removable
        for (auto& e : invocations) {
            if (!suspicious[e[0]] && suspicious[e[1]]) { // a 外部、b 內部 / a outside, b inside
                canRemove = false;                       // 違規，不能移除 / violation, keep all
                break;                                   // 一個就夠 / one is enough
            }
        }

        vector<int> ans;                                // 結果陣列 / answer
        ans.reserve(n);                                 // 預留空間避免多次擴容 / reserve to avoid regrow
        if (canRemove) {                                // 可以移除 -> 留下非可疑 / keep non-suspicious
            for (int i = 0; i < n; i++)
                if (!suspicious[i]) ans.push_back(i);
        } else {                                        // 不能移除 -> 全部保留 / keep everything
            for (int i = 0; i < n; i++)
                ans.push_back(i);
        }
        return ans;                                     // 回傳結果 / return the answer
    }
};

複雜度 / Complexity

Time: O(n + m)，其中 m = invocations.length。建鄰接表掃過每條邊一次 O(m)；DFS 每個節點與每條邊最多各處理一次 O(n + m)；掃邊判斷 O(m)；收集結果 O(n)。加總後由 O(n + m) 主導。/ Building the list, the DFS (each node/edge visited once thanks to the visited marks), the edge scan, and the collection each cost at most O(n + m); the total is dominated by O(n + m).
Space: O(n + m)。鄰接表存所有邊 O(m)，suspicious、stack、結果陣列各 O(n)。/ The adjacency list holds all edges O(m); the visited array, the DFS stack, and the answer are each O(n).

Pitfalls & Edge Cases

有環圖 / cycles：範例三 [[1,2],[0,1],[2,0]] 形成一個環。若 DFS 不用 suspicious/visited 標記就會無限迴圈。程式碼在推入堆疊「之前」就標記，確保每個節點只進堆疊一次。/ Without the visited check, a cycle loops forever; we mark a node before pushing it so it enters the stack only once.
遞迴過深 / recursion depth：n 可達 10^5，純遞迴 DFS 可能 stack overflow。這裡改用明確的陣列堆疊做迭代式 DFS。/ With n up to 10^5, recursive DFS can overflow the call stack; we use an explicit stack instead.
回傳長度 / returnSize (C)：LeetCode 的 C 介面靠 *returnSize 得知陣列長度，忘了設定會讀到垃圾值或錯誤輸出。務必寫入 cnt。/ The C judge reads the length from *returnSize; forgetting to set it yields garbage output.
邊數可能為 0 / empty invocations：invocations 可能是空的。此時沒有任何呼叫，只有 k 可疑，直接回傳其餘節點。C 版對 malloc(0) 用 m>0?m:1 保護，避免未定義行為。/ With no edges, only k is suspicious; the C code guards malloc(0) with m>0?m:1.
判斷方向別搞反 / direction of the check：違規是「a 非可疑、b 可疑」（外→內），不是反過來。可疑方法呼叫外部方法是完全允許的。/ The violation is non-suspicious a → suspicious b (outside calling in); a suspicious method calling outward is perfectly fine.
「不可移除」時回傳全部而非空 / return-all vs return-empty：題目說無法移除時「一個都不移除」，所以回傳 0..n-1，不是空陣列。/ When removal is impossible, return every method, not an empty list.