Advertisement
yimengael

Complete All Course With dependencies

Mar 8th, 2022
980
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.19 KB | None | 0 0
  1.  
  2.     static Boolean can_be_completed(Integer n, ArrayList<Integer> a, ArrayList<Integer> b) {
  3.         //Build the graph
  4.         Map<Integer, ArrayList<Integer>> adj_list = new HashMap<>();
  5.         for (int course = 0; course < n; course++) {
  6.             adj_list.put(course, new ArrayList<>());
  7.         }
  8.         for (int i = 0; i < a.size(); i++) {
  9.             adj_list.get(b.get(i)).add(a.get(i));
  10.         }
  11.        
  12.         // Caculating if we can complete the courses
  13.         int[] visited = new int[n];
  14.         for (int course = 0; course < n; course++) {
  15.             if (visited[course] == 0) {
  16.                 if (!dfs(course, visited, adj_list)) {
  17.                     return false;
  18.                 }
  19.             }
  20.         }
  21.        
  22.         return true;
  23.     }
  24.  
  25.     static Boolean dfs(int course, int[] visited, Map<Integer, ArrayList<Integer>> adj_list) {
  26.         visited[course] = 1;
  27.        
  28.         for (int courseNeighbor : adj_list.get(course)) {
  29.             if (visited[courseNeighbor] == 0) {
  30.                 if (!dfs(courseNeighbor, visited, adj_list)) {
  31.                     return false;
  32.                 }
  33.             }
  34.         }
  35.        
  36.         return true;
  37.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement