Solution

Approach 1: Depth First Search

Intuition and Algorithm

Let G be the graph with all the nodes from initial removed.

For each node v not in initial, we want to know which nodes u from initial can reach v in the graph G [with u (and its edges) added to G]. Let's say these nodes u "infect" v.

Afterwards, we want to know which nodes v are uniquely infected by only one u. For each such pair, it contributes 1 to the answer for u.

Please see the inline comments for more details.

Complexity Analysis

• Time Complexity: $$O(N^2)$$ , where $$N$$ is the length of graph, as the graph is given in adjacent matrix form.

• Space Complexity: $$O(N)$$ .
  
  

Approach 2: Union-Find

Intuition

Let G be the graph with all the nodes in initial removed. For each component of G, either it neighbors 0, 1, or >= 2 nodes from initial. The result only changes if there is exactly 1 neighbor from initial, so we need a way to count this.

Algorithm

It is clear that we will need to consider components of the graph. A "Disjoint Set Union" (DSU) data structure is ideal for this.

We will skip the explanation of how a DSU structure is implemented. Please refer to https://leetcode.com/problems/redundant-connection/solution/ for a tutorial on DSU.

As above, lets consider the components of G: the graph without any nodes from initial.

Then, for every edge uv in the original graph, where u is in initial and v is not, we can count that the component at v of G neighbors 1 more infected node.

Now, for each node u in initial, for each component of G it neighbors, if that component would only be infected by u ("uniquely infected"), then the size of that component contributes to the answer for removing u.

We take the best possible answer.

Complexity Analysis

• Time Complexity: $$O(N^2)$$ , where $$N$$ is the length of graph, as the graph is given in adjacent matrix form.

• Space Complexity: $$O(N)$$ .
  
  

Analysis written by: @awice.