_1376.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.HashSet;
importjava.util.List;
importjava.util.Map;
importjava.util.Set;

publicclass_1376 {
publicstaticclassSolution1 {
intmaxMinutes = 0;

publicintnumOfMinutes(intn, intheadID, int[] manager, int[] informTime) {
boolean[] visited = newboolean[manager.length];
Set<Integer> managerIdSet = newHashSet<>();
for (intid : manager) {
managerIdSet.add(id);
 }
Set<Integer> visitedEmployees = newHashSet<>();
for (inti = 0; i < n; i++) {
visitedEmployees.add(i);
 }

Map<Integer, List<Integer>> map = newHashMap<>();
for (inti = 0; i < manager.length; i++) {
if (!map.containsKey(manager[i])) {
map.put(manager[i], newArrayList<>());
 }
map.get(manager[i]).add(i);
 }
backtracking(visited, headID, 0, informTime, managerIdSet, visitedEmployees, map);
returnmaxMinutes;
 }

privatevoidbacktracking(
boolean[] visited,
intmanagerId,
intcurrentMinutes,
int[] informTime,
Set<Integer> managerIdSet,
Set<Integer> visitedEmployees,
Map<Integer, List<Integer>> map) {
if (visitedEmployees.contains(managerId)) {
visitedEmployees.remove(managerId);
 }
if (!managerIdSet.contains(managerId)) {
maxMinutes = Math.max(currentMinutes, maxMinutes);
return;
 }
if (visitedEmployees.isEmpty()) {
return;
 }
visited[managerId] = true;
if (map.containsKey(managerId)) {
List<Integer> suboridnates = map.get(managerId);
for (intsubordinate : suboridnates) {
if (!visited[subordinate]) {
backtracking(
visited,
subordinate,
currentMinutes + informTime[managerId],
informTime,
managerIdSet,
visitedEmployees,
map);
 }
 }
 }
 }
 }
}