LeetCode(65) -- 207

P207. Course Schedule (Medium)

有n门课，用0到n-1表示。有一些课有前置课，如果0的前置课为1，就表示为[0,1]。 问是否可以完成所有课程。

我的思路

这道题本质上就是问一个有向图中，有没有环的问题。

讨论区

dfs

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        boolean[] visited = new boolean[numCourses];

        for (int i = 0; i < prerequisites.length; i++) {
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if (!dfs(graph, visited, i)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(ArrayList[] graph, boolean[] visited, int course) {
        if (visited[course]) {
            return false;
        } else {
            visited[course] = true;
        }

        for (int i = 0; i < graph[course].size(); i++) {
            if (!dfs(graph, visited, (int)graph[course].get(i))) {
                return false;
            }
        }
        visited[course] = false;
        return true;
    }
}

16%

最优解

public class P207_CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0) {
            return true;
        }

        int[] in = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            in[prerequisites[i][1]]++;
        }

        boolean[] visited = new boolean[prerequisites.length];
        boolean change = true;
        while (change) {
            change = false;
            for (int i = 0; i < prerequisites.length; i++) {
                if (!visited[i]) {
                    if (in[prerequisites[i][0]] == 0 && in[prerequisites[i][1]] != 0) {
                        visited[i] = true;
                        in[prerequisites[i][1]]--;
                        change = true;
                    }
                }
            }
        }
        for (int i = 0; i < numCourses; i++) {
            if (in[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Graph graph = new Graph(numCourses);
        for(int i = 0; i < prerequisites.length; i++){
            graph.addEdge(prerequisites[i][0],prerequisites[i][1]);
        }
        
        return graph.canFinish();
    }
}

class Edge{
    public int destination;
    public Edge next;
}

class Graph{
    int vertices;
    int[] visited;
    Edge[] edges;
    boolean[] inStack;
    boolean isCyclic = false;
    Graph(int vertices){
        this.vertices = vertices;
        visited = new int[vertices];
        inStack = new boolean[vertices];
        edges = new Edge[vertices];
    }
    
    public void addEdge(int source, int destination){
        Edge edge = new Edge();
        edge.destination = destination;
        
        Edge lastEdge = edges[source];
        if(lastEdge == null){
            edges[source] = edge;
        }else{
            while(lastEdge.next != null){
                lastEdge = lastEdge.next;
            }
            
            lastEdge.next = edge;
        }
    }
    
    public boolean canFinish(){
        int flag = 0;
        for(int i = 0; i < visited.length; i++){
            if(visited[i] == 0){
                flag++;
                dfs(i, flag);
            }
        }
        
        return !isCyclic;
    }
    
    public void dfs(int vertex, int flag){
        visited[vertex] = flag;
        inStack[vertex] = true;
        
        Edge edge = edges[vertex];
        while(edge != null){
            int destination = edge.destination;
            if(visited[destination] == 0){
                dfs(destination, flag);
            }else if(inStack[destination]){
                isCyclic = true;
            }
            
            edge = edge.next;
        }
        
        inStack[vertex] = false;
    }   
    
}