var curComponentInfectedNodeCnt = 0
var infectedNode = Int.MAX_VALUE

fun minMalwareSpread(graph: Array<IntArray>, initial: IntArray): Int {
    // To adjacency list
    val adjacencyList =  Array<ArrayList<Int>>(graph.size) {
        ArrayList()
    }
    // For each vertex
    for (i in 0..graph.lastIndex) {
        val curVertexNeighbors = graph[i]
        // For each neighbor
        for (j in 0..graph.lastIndex) {
            if (curVertexNeighbors[j] == 0) continue
            adjacencyList[i].add(j)
        }
    }

    val initialInfectedNodes = initial.toHashSet()
    val used = HashSet<Int>()
    val connectivityComponents = ArrayList<ArrayList<Int>>()
    var maxComponentSize = Int.MIN_VALUE
    var nodeToBeRemoved = Int.MAX_VALUE
    // For each vertex
    for (i in 0..adjacencyList.lastIndex) {
        val neighbors = adjacencyList[i]
        // For each neighbor
        for (j in 0..neighbors.lastIndex) {
            if (used.contains(neighbors[j])) continue
            connectivityComponents.add(ArrayList())
            curComponentInfectedNodeCnt = 0
            dfs(adjacencyList, connectivityComponents.last(), used, initialInfectedNodes, neighbors[j])

            if (curComponentInfectedNodeCnt == 1) {
                val curComponentSize = connectivityComponents.last().size
                if (curComponentSize == maxComponentSize && infectedNode < nodeToBeRemoved) {
                    nodeToBeRemoved = infectedNode
                } else if (curComponentSize > maxComponentSize) {
                    nodeToBeRemoved = infectedNode
                    maxComponentSize = curComponentSize
                }
            }
        }
    }
    return if (nodeToBeRemoved == Int.MAX_VALUE) initial.min() else nodeToBeRemoved
}

fun dfs(
    adjacencyList: Array<ArrayList<Int>>,
    componentNodes: ArrayList<Int>,
    used: HashSet<Int>,
    initialInfectedNodes: HashSet<Int>,
    curNode: Int
) {
    if (initialInfectedNodes.contains(curNode)) {
        ++curComponentInfectedNodeCnt
        infectedNode = curNode
    }

    used.add(curNode)
    componentNodes.add(curNode)

    val neighbors = adjacencyList[curNode]
    for (i in 0..neighbors.lastIndex) {
        val neighborVertex = neighbors[i]
        if (used.contains(neighborVertex)) continue
        dfs(adjacencyList, componentNodes, used, initialInfectedNodes, neighborVertex)
    }
}