import java.util.*;

/**
 * 
 * @author Mahsa Sadi 
 * @since 2020-02-20
 *
 */
public class MalwareSpreadMinimizerV2 implements MalwareSpreadMinimizer {

	/**
	 * Problem: Minimize the spread of malware
	 * 
	 * 
	 * 
	 * 
	 * Description:
	 * 
	 * In a network of nodes, each node i is directly connected to another node j if
	 * and only if graph[i][j] = 1. Some nodes initial are initially infected by
	 * malware. Whenever two nodes are directly connected and at least one of those
	 * two nodes is infected by malware, both nodes will be infected by malware.
	 * This spread of malware will continue until no more nodes can be infected in
	 * this manner. Suppose M(initial) is the final number of nodes infected with
	 * malware in the entire network, after the spread of malware stops. We will
	 * remove one node from the initial list. Return the node that if removed, would
	 * minimize M(initial). If multiple nodes could be removed to minimize
	 * M(initial), return such a node with the smallest index. Note that if a node
	 * was removed from the initial list of infected nodes, it may still be infected
	 * later as a result of the malware spread.
	 * 
	 * 
	 * Note: 1 < graph.length = graph[0].length <= 300 0 <= graph[i][j] ==
	 * graph[j][i] <= 1 graph[i][i] = 1 1 <= initial.length < graph.length 0 <=
	 * initial[i] < graph.length
	 * 
	 * 
	 * 
	 * 
	 * 
	 * Solution:
	 * 
	 * 1 - For each given infected node in the given graph find the maximum
	 * neighborhood tree.
	 * 
	 * 2- Return the node with the largest maximum tree and the smallest index
	 * 
	 * 
	 * 
	 * 
	 * Find the Maximum Neighborhood Tree for a Given Node in a Given Graph:
	 * 
	 * == Breadth-First Traversal of the Graph Starting from the Given Node:
	 * 
	 * 1- Start from a given node.
	 * 
	 * 2- Visit neighbors if not visited.
	 * 
	 * 3- Repeat the visit for each neighbor.
	 * 
	 * 4- Repeat until no new neighbors can be visited.
	 * 
	 * 5- Record the count of visited nodes starting from the given node
	 * 
	 * 
	 * 
	 * 
	 */

	int[] sizeOfMaxNeighborhoodTree;

	public int minMalwareSpread(int[][] graph, int[] initial) {

		int mostInfluentialNode = -1;
		int maxReachableNodes = -1;

		sizeOfMaxNeighborhoodTree = new int[graph[0].length];
		initializeArray(sizeOfMaxNeighborhoodTree, -1);

		for (Integer infectedNode : initial) {
			sizeOfMaxNeighborhoodTree[infectedNode] = findLengthOfMaxNeighborhoodTree(graph, infectedNode);

			if (maxReachableNodes <= sizeOfMaxNeighborhoodTree[infectedNode]
					&& (infectedNode < mostInfluentialNode || mostInfluentialNode == -1)) {
				maxReachableNodes = sizeOfMaxNeighborhoodTree[infectedNode];
				mostInfluentialNode = infectedNode;
			}
		}

		return mostInfluentialNode;
	}

	public void initializeArray(int[] array, int initialziationValue) {
		for (int i = 0; i < array.length; i++) {
			array[i] = initialziationValue;
		}
	}

	public int findLengthOfMaxNeighborhoodTree(int[][] graph, int infectedNode) {
		int numberOfNodes = graph[0].length;
		int[] visitedNodes = new int[numberOfNodes];

		List<Integer> nodesToBeVisited = new ArrayList<Integer>();

		int sizeOfMaxNeighborhoodTreeFromThisNode = 0;

		nodesToBeVisited.add(infectedNode);

		/**
		 * Breadth-First Traversal of Infected Node
		 */

		while (!nodesToBeVisited.isEmpty()) {

			int currentNode = nodesToBeVisited.remove(0);

			if (sizeOfMaxNeighborhoodTree[currentNode] == -1) {

				visitedNodes[currentNode] = 1;

				for (int i = 0; i < graph[currentNode].length; i++) {

					if (graph[currentNode][i] == 1 && visitedNodes[i] == 0) {
						visitedNodes[i] = 1;
						nodesToBeVisited.add(i);
						sizeOfMaxNeighborhoodTreeFromThisNode++;
					}

				}
			}

			else {
				sizeOfMaxNeighborhoodTreeFromThisNode += sizeOfMaxNeighborhoodTree[currentNode];
			}

		}

		return sizeOfMaxNeighborhoodTreeFromThisNode;

	}

}