Solution
Approach 1: Depth First Search
Intuition
First, let's color (the nodes of) each component of the graph. We can do this using a depth first search.
Afterwards, notice that if two nodes in initial
have the same color (ie., belong to the same component), then removing them from initial
won't decrease M(initial)
. This is because the malware will spread to reach every node in this component no matter what.
So, among nodes with a unique color in initial
, we will remove the node with the largest component size. (If there's a tie, we return the smallest index. Also, if there aren't any nodes with a unique color, we'll just return the smallest index node.)
Algorithm
This algorithm has a few parts:

Coloring each component: For each node, if it isn't yet colored, use a depthfirst search to traverse its component, coloring that component with a new color.

Size of each color: Count the number of occurrences of each color.

Find unique colors: Look at the colors of nodes in
initial
to see which nodes have unique colors. 
Choose answer: For each node with a unique color, find the size of that color. The largest size is selected, with ties broken by lowest node number.
 If there is no node with a unique color, the answer is
min(initial)
.
 If there is no node with a unique color, the answer is
Complexity Analysis

Time Complexity: , where is the length of
graph
, as the graph is given in adjacent matrix form. 
Space Complexity: .
Approach 2: UnionFind
Intuition and Algorithm
As in Approach 1, 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/redundantconnection/solution/ for a tutorial on DSU.
To our DSU, we can keep a side count of the size of each component. Whenever we union two components together, the size of those components are added.
With these details neatly handled by our DSU structure, we can continue in a similar manner to Approach 1: for each node in initial
with a unique color, we will consider it as a candidate answer. If no node in initial
have a unique color, then we will take min(initial)
as the answer.
Note that for brevity, our DSU
implementation does not use unionbyrank. This makes the asymptotic time complexity larger.
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.