SHARE
TWEET

Untitled

a guest Feb 18th, 2020 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.    public static boolean canFinish(int numCourses, int[][] prerequisites)  {
  3.        Integer[][] list = new Integer[prerequisites.length][];
  4.        for (int i = 0; i < prerequisites.length; i++)  {
  5.            list[i] = new Integer[prerequisites[i].length];
  6.            for (int j = 0; j < prerequisites[i].length; j++)  {
  7.                list[i][j] = prerequisites[i][j];
  8.            }
  9.        }
  10.        
  11.        return canFinish1(numCourses, list);
  12.    }
  13.    
  14.       public static <T> boolean canFinish1(int numCourses, T[][] prerequisites) {
  15.         int rescount = 0;
  16.         //build graph using adjacency list. array of arraylists.
  17.         Map< T, ArrayList<T>> graph = new HashMap<>();
  18.         Map<T, Integer> inDegrees = new HashMap<>(numCourses);
  19.  
  20.         //add the edges to the graph.
  21.         for (int i = 0; i < prerequisites.length; i++) {
  22.             T firstClass = prerequisites[i][0];
  23.             T secondClass = prerequisites[i][1];
  24.             graph.putIfAbsent(firstClass, new ArrayList<>());
  25.             graph.get(firstClass).add(secondClass);
  26.             graph.putIfAbsent(secondClass, new ArrayList<>());
  27.             //since second class depends on first class, increase the indegree of second class.
  28.             inDegrees.putIfAbsent(firstClass, 0);
  29.             inDegrees.putIfAbsent(secondClass, 0);
  30.  
  31.             inDegrees.put(secondClass, inDegrees.get(secondClass) + 1);
  32.         }
  33.  
  34.         Stack< T > stack = new Stack < > ();
  35.         for (T key: inDegrees.keySet()) {
  36.             if (inDegrees.get(key)==0) {
  37.                 stack.push(key);
  38.             }
  39.         }
  40.  
  41.         //DFS basically
  42.         while (stack.size() > 0) {
  43.             T a = stack.pop();
  44.             rescount++;
  45.             //neighbors
  46.             for (T node: graph.get(a)) {
  47.                 inDegrees.put(node, inDegrees.get(node)- 1);
  48.                 if (inDegrees.get(node) == 0) {
  49.                     stack.push(node);
  50.                 }
  51.             }
  52.         }
  53.  
  54.  
  55.         if (rescount == numCourses || (inDegrees.size() == rescount)) {
  56.             return true;
  57.         }
  58.  
  59.         if (inDegrees.size() == 0)  {
  60.             return true;
  61.         }
  62.  
  63.         return false;
  64.     }
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top