Solution


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 depth-first 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).

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 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/redundant-connection/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 union-by-rank. 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.