Programming

Leetcode-207. Course Schedule

By PattySung 04 January 2024
Leetcode-207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

<解題>


class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        
        for (int[] pair : prerequisites) {
            // pair[1]是先修課程，pair[0]是後修課程
            indegree[pair[0]]++; // 後修課程的入度加1
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) { // 入度為0的課程，可以直接修
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int curr = queue.poll(); // 從隊列中取出當前可以修的課程

            for (int[] pair : prerequisites) {
                if (pair[1] == curr) { // 找到有curr作為先修的課程
                    indegree[pair[0]]--; // 後修課程的入度減1
                    if (indegree[pair[0]] == 0) {
                        queue.offer(pair[0]); // 如果後修課程的入度變為0，則可以修
                    }
                }
            }
        }

        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] != 0) { // 如果還有入度不為0的課程，表示無法完成所有課程
                return false;
            }
        }
        return true;
    }
}

T: O(numCourses + prerequisites.length) S: O(numCourses)

拓撲排序

拓撲排序（Topological Sorting）是一種用於有向無環圖（DAG）的節點排序算法，其中節點代表一些對象，有向邊代表對象之間的依賴關係。拓撲排序的目標是找到一個節點的線性排序，使得對於每一條有向邊 (u, v)，節點 u 在排序中出現在節點 v 之前。換句話說，它能夠找到一種順序，使得所有的依賴關係都被滿足。

拓撲排序常用於解決以下問題：

1.任務調度：例如，課程安排、作業調度等。 2.編譯順序：編譯器需要確保所有的依賴項被按正確的順序編譯。 3.資源分配：在分配資源時需要確保資源之間的依賴性。 4.地圖繪製：在地圖繪製中，城市之間的道路或飛行路線可以表示為有向無環圖，拓撲排序可用於找到最佳路線。

拓撲排序可以通過不同的演算法來實現，其中最常見的演算法包括：

1.Kahn’s Algorithm：這是一種基於入度的方法，通過選擇入度為0的節點，然後移除相關邊來構建排序序列。 2.Depth-First Search (DFS)：使用深度優先搜索遍歷有向圖，並在遍歷過程中按照反向順序將節點添加到排序序列中。 3.Breadth-First Search (BFS)：使用廣度優先搜索來構建排序序列，類似於Kahn’s Algorithm，但是使用隊列而不是堆棧。

1. Kahn’s Algorithm (基於入度的方法)

假設我們有一個有向圖的邊列表 edges，以及節點數量 numCourses，我們可以使用Kahn’s Algorithm 來進行拓撲排序。這是一個基於入度的方法。

Copy code
import java.util.*;

public class TopologicalSortKahn {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        // Calculate indegree for each course
        for (int[] edge : prerequisites) {
            indegree[edge[0]]++;
        }

        // Add courses with indegree 0 to the queue
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int course = queue.poll();
            result.add(course);

            for (int[] edge : prerequisites) {
                if (edge[1] == course) {
                    indegree[edge[0]]--;
                    if (indegree[edge[0]] == 0) {
                        queue.offer(edge[0]);
                    }
                }
            }
        }

        if (result.size() != numCourses) {
            return new int[0]; // No valid ordering
        }

        int[] order = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            order[i] = result.get(i);
        }

        return order;
    }
}

2. Depth-First Search (DFS) 方法

使用深度優先搜索 (DFS) 來進行拓撲排序。這個示例假設我們有一個有向圖的鄰接表 adjList 和節點數量 numCourses。

Copy code
import java.util.*;

public class TopologicalSortDFS {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int[] edge : prerequisites) {
            adjList.putIfAbsent(edge[1], new ArrayList<>());
            adjList.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[numCourses];
        boolean[] onStack = new boolean[numCourses];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && hasCycle(i, adjList, visited, onStack, stack)) {
                return new int[0]; // Cycle detected, no valid ordering
            }
        }

        int[] order = new int[numCourses];
        for (int i = 0; !stack.isEmpty(); i++) {
            order[i] = stack.pop();
        }

        return order;
    }

    private boolean hasCycle(int course, Map<Integer, List<Integer>> adjList, boolean[] visited, boolean[] onStack, Stack<Integer> stack) {
        visited[course] = true;
        onStack[course] = true;

        if (adjList.containsKey(course)) {
            for (int neighbor : adjList.get(course)) {
                if (!visited[neighbor]) {
                    if (hasCycle(neighbor, adjList, visited, onStack, stack)) {
                        return true;
                    }
                } else if (onStack[neighbor]) {
                    return true;
                }
            }
        }

        onStack[course] = false;
        stack.push(course);

        return false;
    }
}

3. Breadth-First Search (BFS) 方法

使用廣度優先搜索 (BFS) 來進行拓撲排序。這個示例也假設我們有一個有向圖的鄰接表 adjList 和節點數量 numCourses。

Copy code
import java.util.*;

public class TopologicalSortBFS {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        int[] indegree = new int[numCourses];

        for (int[] edge : prerequisites) {
            adjList.putIfAbsent(edge[1], new ArrayList<>());
            adjList.get(edge[1]).add(edge[0]);
            indegree[edge[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] order = new int[numCourses];
        int index = 0;

        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[index++] = course;

            if (adjList.containsKey(course)) {
                for (int neighbor : adjList.get(course)) {
                    indegree[neighbor]--;
                    if (indegree[neighbor] == 0) {
                        queue.offer(neighbor);
                    }
                }
            }
        }

        return index == numCourses ? order : new int[0]; // No valid ordering if not all courses are included
    }
}