Graph day start!

Parallel Courses

Q: https://leetcode.com/problems/parallel-courses/

classic topic sort issue

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        int[] inboundsByCourse = new int[n+1];
        Map<Integer, Set<Integer>> outBoundsByCourse = new HashMap<>();
        Set<Integer> studiedCourses = new HashSet<>();
        for (int[] relation : relations) {
            inboundsByCourse[relation[1]]++;
            if (!outBoundsByCourse.containsKey(relation[0])) {
                outBoundsByCourse.put(relation[0], new HashSet<>());
            }
            outBoundsByCourse.get(relation[0]).add(relation[1]);
        }
        Queue<Integer> needStudy = new LinkedList<>();
        int studyCount = 0;
        for (int i = 1;i <= n;i++) {
            if (inboundsByCourse[i] == 0) {
                needStudy.offer(i);
                studiedCourses.add(i);
            }
        }
        while(!needStudy.isEmpty()) {
            studyCount++;
            List<Integer> studyCourses = new ArrayList<>();
            while(!needStudy.isEmpty()) {
                studyCourses.add(needStudy.poll());
            }
            for (Integer studyCourse : studyCourses) {
                if (outBoundsByCourse.containsKey(studyCourse)) {
                    for (Integer outBound : outBoundsByCourse.get(studyCourse)) {
                        inboundsByCourse[outBound]--;
                    }
                }
            }
            for (int i = 1;i <= n;i++) {
                if (inboundsByCourse[i] == 0 && !studiedCourses.contains(i)) {
                    needStudy.offer(i);
                    studiedCourses.add(i);
                }
            }
        }
        return studiedCourses.size() == n ? studyCount : -1;
    }
}

Reconstruct Itinerary

Q: https://leetcode.com/problems/reconstruct-itinerary/

backtracking

class Solution {
  // origin -> list of destinations
  HashMap<String, List<String>> flightMap = new HashMap<>();
  HashMap<String, boolean[]> visitBitmap = new HashMap<>();
  int flights = 0;
  List<String> result = null;


  public List<String> findItinerary(List<List<String>> tickets) {
    // Step 1). build the graph first
    for (List<String> ticket : tickets) {
      String origin = ticket.get(0);
      String dest = ticket.get(1);
      if (this.flightMap.containsKey(origin)) {
        List<String> destList = this.flightMap.get(origin);
        destList.add(dest);
      } else {
        List<String> destList = new LinkedList<String>();
        destList.add(dest);
        this.flightMap.put(origin, destList);
      }
    }

    // Step 2). order the destinations and init the visit bitmap
    for (Map.Entry<String, List<String>> entry : this.flightMap.entrySet()) {
      Collections.sort(entry.getValue());
      this.visitBitmap.put(entry.getKey(), new boolean[entry.getValue().size()]);
    }

    this.flights = tickets.size();
    LinkedList<String> route = new LinkedList<String>();
    route.add("JFK");

    // Step 3). backtracking
    this.backtracking("JFK", route);
    return this.result;
  }

  protected boolean backtracking(String origin, LinkedList<String> route) {
    if (route.size() == this.flights + 1) {
      this.result = (List<String>) route.clone();
      return true;
    }

    if (!this.flightMap.containsKey(origin))
      return false;

    int i = 0;
    boolean[] bitmap = this.visitBitmap.get(origin);

    for (String dest : this.flightMap.get(origin)) {
      if (!bitmap[i]) {
        bitmap[i] = true;
        route.add(dest);
        boolean ret = this.backtracking(dest, route);
        route.pollLast();
        bitmap[i] = false;

        if (ret)
          return true;
      }
      ++i;
    }

    return false;
  }
}

Largest Color Value in a Directed Graph

Q: https://leetcode.com/problems/largest-color-value-in-a-directed-graph/

class Solution {
  public int largestPathValue(String colors, int[][] edges) {
        int n = colors.length();
        Map<Integer, List<Integer>> adj = new HashMap<>();
        int[] indegree = new int[n];

        for (int[] edge : edges) {
            adj.computeIfAbsent(edge[0], k->new ArrayList<Integer>()).add(edge[1]);
            indegree[edge[1]]++;
        }

        int[][] count = new int[n][26];
        Queue<Integer> q = new LinkedList<>();

        // Push all the nodes with indegree zero in the queue.
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        int answer = 1, nodesSeen = 0;
        while (!q.isEmpty()) {
            int node = q.poll();
            answer = Math.max(answer, ++count[node][colors.charAt(node) - 'a']);
            nodesSeen++;

            if (!adj.containsKey(node)) {
                continue;
            }

            for (int neighbor : adj.get(node)) {
                for (int i = 0; i < 26; i++) {
                    // Try to update the frequency of colors for the neighbor to include paths
                    // that use node->neighbor edge.
                    count[neighbor][i] = Math.max(count[neighbor][i], count[node][i]);
                }

                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.offer(neighbor);
                }
            }
        }

        return nodesSeen < n ? -1 : answer;
    }
}

Note

• 有向圖可以用 topological sort
• 先把edge都換成圖 node有編號比較好思考