3310. Remove Methods From Project
Approach
DFS from suspicious nodes; mark reachable from invocations; exclude from result.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
Union-Find (Disjoint Set Union) tracks connected components efficiently. Operations: Find (with path compression) and Union (by rank). Achieves near-O(1) per operation (O(α(n)) amortized). Classic uses: Kruskal's MST, detecting undirected graph cycles, and grouping equivalent elements.
// Approach: DFS from suspicious nodes; mark reachable from invocations; exclude from result.
// Time: O(n + E) Space: O(n)
public class Solution
{
private bool[] suspicious;
private bool[] vis;
private List<int>[] f;
private List<int>[] g;
public IList<int> RemainingMethods(int n, int k, int[][] invocations)
{
suspicious = new bool[n];
vis = new bool[n];
f = new List<int>[n];
g = new List<int>[n];
for (int i = 0; i < n; i++)
{
f[i] = new List<int>();
g[i] = new List<int>();
}
foreach (var e in invocations)
{
int a = e[0], b = e[1];
f[a].Add(b);
f[b].Add(a);
g[a].Add(b);
}
Dfs(k);
for (int i = 0; i < n; ++i)
{
if (!suspicious[i] && !vis[i])
Dfs2(i);
}
List<int> ans = new List<int>();
for (int i = 0; i < n; ++i)
{
if (!suspicious[i])
ans.Add(i);
}
return ans;
}
private void Dfs(int i)
{
suspicious[i] = true;
foreach (int j in g[i])
{
if (!suspicious[j])
Dfs(j);
}
}
private void Dfs2(int i)
{
vis[i] = true;
foreach (int j in f[i])
{
if (!vis[j])
{
suspicious[j] = false;
Dfs2(j);
}
}
}
}