https://leetcode-cn.com/problems/minimize-malware-spread/submissions/
关于这道恶意软件传播问题，也是一道图论问题，并且可以使用这个课程的dfs算法解决我有一个思路，但是该思路其实比较复杂， 希望通过讨论能得到更加清晰的思路。以下是我的思路：

1. 这同样是一个图论题，只是图的表示使用了邻接矩阵的表示法
2. 一个被污染节点与另外一个节点连接，就能污染另一个节点；这说明了一个联通分量中只要有一个节点被污染，那么整个联通分量都会被污染
3. 因此，若想要在initial数组中删除一个元素使得最终被污染节点最少，只有以下三种情况：
   ①整张图只有一个联通分量 -> 无论减少initial中的哪一个结点，都是一样的，直接返回initial中的最小值即可
   ②整张图有多个联通分量 ->
   1）若该图的所有联通分量都至少包含initial数组中的两个顶点，则无论删除谁都是一样的(因为对于每个联通分量，删 除其中一个污染结点，另外一个污染节点仍会污染整个联通分量)，直接返回initial中的最小值即可
   2）若该图有至少一个联通分量只包含initial数组中的一个顶点，那么返回这些联通分量中面积最大的联通分量所对应的initial值
4. 最后，关于联通分量面积(part)，联通分量id(visited)，以及返回值ret，我总结了以下关系：
   part[visited[ret]] -> MAX
   visited[ret] -> ret唯一
   ret -> MIN
   ps.写得有点乱，希望大家见谅，也希望老师能够给出更好的思路，简化编写代码过程的逻辑
   以下是我的代码(通过leetcode的测试)，代码编写得比较乱(写了比较久，脑袋都被自己转晕了)，见谅：

import java.util.*;

class Solution {
    private int[][] graph;
    private int[] visited;
    private int cccount = 0;
    private int RC;
    public int minMalwareSpread(int[][] graph, int[] initial) {
        this.graph = graph;
        RC = graph.length;
        visited = new int[RC];
        for(int v = 0; v < RC; v ++)
            visited[v] = -1;
        for(int v = 0; v < RC; v ++)
            if(visited[v] == -1) {
                dfs(v);
                cccount ++;
            }
        Arrays.sort(initial);//对initial进行排序，方便值返回
        if(cccount == 1) return initial[0];

        int[] part = new int[cccount];//通过part数组记录各个联通分量的面积大小
        for(int v = 0; v < RC; v ++)
            part[visited[v]] ++;

        //key: ccid, value: time
        HashMap<Integer, Integer> numOfNode = new HashMap<>();//记录每个联通分量有多少个元素在initial中(即每个联通分量有多少个结点被污染)
        for(int num: initial)
            if(numOfNode.containsKey(visited[num]))
                numOfNode.put(visited[num], numOfNode.get(visited[num]) + 1);
            else
                numOfNode.put(visited[num], 1);

        ArrayList<Integer> set = new ArrayList<>();//找出那些只有一个节点被污染的联通分量，id放入set中
        for(Map.Entry<Integer, Integer> entry: numOfNode.entrySet())
            if(entry.getValue() == 1)
                set.add(entry.getKey());

        if(set.size() == 0) return initial[0];//如果所有联通分量都未被污染，或者至少也有两个结点被污染，那么initial中减少哪个节点结果都一样
        int maxPartKey = set.get(0);//找出只有一个结点被污染的联通分量中最大的一个
        for(int i = 1; i < set.size(); i ++)
            if(part[maxPartKey] < part[set.get(i)]) maxPartKey = set.get(i);

        ArrayList<Integer> maxPart = new ArrayList<>();//因为可能有多个被污染的连通分量面积都是最大的，所以还要将他们放到一个列表中
        for(int i = 0; i < set.size(); i ++)
            if(part[maxPartKey] == part[set.get(i)]) maxPart.add(set.get(i));

        int ret = initial[0];
        for(int i = 0; i < initial.length; i ++)
            if(maxPart.contains(visited[initial[i]])) {
                ret = initial[i];
                break;
            }
        return ret;
    }
    
    private void dfs(int v){
        visited[v] = cccount;
        for(int w: adj(v))
            if(visited[w] == -1)
                dfs(w);
    }

    private ArrayList<Integer> adj(int v){
        ArrayList<Integer> res = new ArrayList<>();
        for(int w = 0; w < RC; w ++)
            if(graph[v][w] == 1 && v != w)
                res.add(w);
        return res;
    }
}