• API
• FAQ
• Tools
• Archive
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<>());
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.
Top