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: , where is the length of
graph
, as the graph is given in adjacent matrix form. -
Space Complexity: .
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: , where is the length of
graph
, as the graph is given in adjacent matrix form. -
Space Complexity: .
Analysis written by: @awice.