Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- static Boolean can_be_completed(Integer n, ArrayList<Integer> a, ArrayList<Integer> b) {
- //Build the graph
- Map<Integer, ArrayList<Integer>> adj_list = new HashMap<>();
- for (int course = 0; course < n; course++) {
- adj_list.put(course, new ArrayList<>());
- }
- for (int i = 0; i < a.size(); i++) {
- adj_list.get(b.get(i)).add(a.get(i));
- }
- // Caculating if we can complete the courses
- int[] visited = new int[n];
- for (int course = 0; course < n; course++) {
- if (visited[course] == 0) {
- if (!dfs(course, visited, adj_list)) {
- return false;
- }
- }
- }
- return true;
- }
- static Boolean dfs(int course, int[] visited, Map<Integer, ArrayList<Integer>> adj_list) {
- visited[course] = 1;
- for (int courseNeighbor : adj_list.get(course)) {
- if (visited[courseNeighbor] == 0) {
- if (!dfs(courseNeighbor, visited, adj_list)) {
- return false;
- }
- }
- }
- return true;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement