Graph

1192. Critical Connections in a Network

Convert edge to graph map. DFS traverse from 0 node, assign new id every time. Use arrays ids[] and low[] to store the corresponding ids and the low index of the connect graph. If next node is unvisited, DFS to next node. Update low[curt] after the traverse by low[curt] = Math.min(low[curt], low[next]). Add to result if ids[curt] < low[next]

int[] ids;
int[] low;
int index = 0;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    this.ids = new int[n];
    this.low = new int[n];
    Arrays.fill(ids, -1);
    Map<Integer, Set<Integer>> graph = buildGraph(connections);
    List<List<Integer>> res = new ArrayList<>();
    dfs(0, -1, graph, res);
    return res;
}

private void dfs(int curt, 
                 int prev, 
                 Map<Integer, Set<Integer>> graph, 
                 List<List<Integer>> res) {
    ids[curt] = low[curt] = index++;
    if (!graph.containsKey(curt)) return;
    for (int next : graph.get(curt)) {
        if (next == prev) continue;
        if (ids[next] == -1) {
            dfs(next, curt, graph, res);
            low[curt] = Math.min(low[curt], low[next]);
            if (ids[curt] < low[next]) {
                res.add(Arrays.asList(curt, next));
            }
        } else {
            low[curt] = Math.min(low[curt], low[next]);
        }
    }
}

private Map<Integer, Set<Integer>> buildGraph(List<List<Integer>> edges) {
    Map<Integer, Set<Integer>> map = new HashMap<>();
    for (List<Integer> e : edges) {
        map.putIfAbsent(e.get(0), new HashSet<>());
        map.putIfAbsent(e.get(1), new HashSet<>());
        map.get(e.get(0)).add(e.get(1));
        map.get(e.get(1)).add(e.get(0));
    }
    return map;
}

1102. Path With Maximum Minimum Value

Use maxHeap to store a new class (val, x, y). Every time it pops the largest node, and maintain a min from the val.

int[][] dirs = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public int maximumMinimumPath(int[][] A) {
    int m = A.length, n = A[0].length;
    PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<>(){
        public int compare(int[] a, int[] b) {
            return b[0] - a[0];
        }
    });
    pq.offer(new int[]{A[0][0], 0, 0});
    A[0][0] = -1;
    int min = Integer.MAX_VALUE;
    while (!pq.isEmpty()) {
        int[] curt = pq.poll();
        min = Math.min(min, curt[0]);
        if (curt[1] == m - 1 && curt[2] == n - 1) break;
        for (int[] d : dirs) {
            int nx = curt[1] + d[0];
            int ny = curt[2] + d[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && A[nx][ny] != -1) {
                pq.offer(new int[]{A[nx][ny], nx, ny});
                A[nx][ny] = -1;
            }
        }
    }
    return min;
}

332. Reconstruct Itinerary

Use PQ instead of Set as we can get the next stops in lexicographical order. DFS to the end of next and use bottom-up to construct itinerary.

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, PriorityQueue<String>> map = new HashMap<>();
    for (List<String> l : tickets) {
        map.putIfAbsent(l.get(0), new PriorityQueue<>());
        map.get(l.get(0)).add(l.get(1));
    }
    List<String> list = new ArrayList<>();
    dfs("JFK", list, map);
    return list;
}

private void dfs(String curt, List<String> list, Map<String, PriorityQueue<String>> map) {
    PriorityQueue<String> pq = map.get(curt);
    while (pq != null && !pq.isEmpty()) {
        String next = pq.poll();
        dfs(next, list, map);
    }
    list.add(0, curt);
}

1376. Time Needed to Inform All Employees

Get the largest time spent on each level.

Java (BFS)

public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for (int i = 0; i < manager.length; i++) {
        int u = manager[i], v = i;
        if (u == -1) {
            continue;
        }
        graph.putIfAbsent(u, new HashSet<>());
        graph.get(u).add(v);
    }
    int totalTime = 0;
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{headID, 0});
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] curt = q.poll();
            int emp = curt[0], time = curt[1];
            totalTime = Math.max(time, totalTime);
            if (graph.get(emp) == null) continue;
            for (int next : graph.get(emp)) {
                q.offer(new int[]{next, time + informTime[emp]});
            }
        }
    }
    return totalTime;
}

Java (DFS)

public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    int res = 0;
    for (int i = 0; i < n; ++i)
        res = Math.max(res, dfs(i, manager, informTime));
    return res;
}
public int dfs(int i, int[] manager, int[] informTime) {
    if (manager[i] != -1) {
        informTime[i] += dfs(manager[i], manager, informTime);
        manager[i] = -1;
    }
    return informTime[i];
}

Java (DFS + construct graph)

public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for (int i = 0; i < manager.length; i++) {
        int u = manager[i], v = i, t = informTime[i];
        if (u == -1) {
            continue;
        }
        graph.putIfAbsent(u, new HashSet<>());
        graph.get(u).add(v);
    }
    return dfs(headID, graph, informTime);
}

private int dfs(int curt, Map<Integer, Set<Integer>> graph, int[] informTime) {
    int max = 0;
    if (graph.get(curt) == null) {
        return 0;
    }
    for (int next : graph.get(curt)) {
        max = Math.max(dfs(next, graph, informTime), max);
    }
    return max + informTime[curt];
}