3310. Remove Methods From Project

MediumView on LeetCode

Array Depth-First Search Union Find Graph

Time: O(n + E)

Space: O(n + E)

Problem Overview

Suspicious methods are k plus everything reachable from k on the directed invocation graph.

Intuition

Suspicious methods are k plus everything reachable from k on the directed invocation graph. You may delete that whole set only if nothing outside calls into it. After marking the directed closure, walk the undirected version of the graph from every safe method and clear the suspicious flag on anything you touch - an outside edge into the set makes removal illegal, so those methods must remain.

Algorithm

1Build g as directed edges a->b from invocations, and f as undirected (both directions).
2DFS from k on g; mark every reachable node suspicious.
3For each still non-suspicious, unvisited i: DFS2 on f, setting suspicious[j] = false for every reached j.
4Return all indices with suspicious[i] == false (any order).

Example Walkthrough

Input: n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]]

1.Directed DFS from 0 marks 0,1,2 as suspicious.
2.Component {3,4} is disjoint, so no undirected path clears those flags from the outside.
3.Removal is legal; remaining methods are 3 and 4.

Output: [3, 4]

Common Pitfalls

•If any outside method can reach a suspicious one undirected, keep the entire connected component - do not delete a partial set.
•Use directed edges only for the initial suspicious closure from k.
•Undirected edges catch reverse invokers that would block deletion.
•If everything is suspicious and removable, the answer can be empty.

3310.cs

// Approach: Directed DFS from k marks the suspicious closure (k and everything
// it can reach via invocations). Undirected edges then flood from every still
// non-suspicious method, clearing the suspicious flag along the connected
// component - any outside reach into the group means removal is illegal, so
// those methods stay. Remaining methods are those with suspicious = false.
// Time: O(n + E) Space: O(n + E)
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);
            }
        }
    }
}

Was this solution helpful?