力扣面试150题--课程表

Day 63

题目描述

做法

初次思路：本质就是将所有前置课程和后置课程作为一个有向图（前者指向后者），判断这个图是否是一个有向无环图（即是否存在拓扑排序）（本质做法是dfs）
做法：

1. 将所有的前置和后置课程初始化为一个邻接矩阵graph
2. 在初始化的过程中找到一个入度为0的课程作为起点进入find函数（这里我的做法比较浪费，直接使用了一个hash数组来找）
3. 进入find函数来找拓扑排序
4. visited判断该点是否访问过，如果访问过，则find函数直接结束，如果没有访问过，将其visited置为1
5. 将这个课程压入栈中
6. 判断所有将这个课程作为前置条件的课程，是否可以作为下一个课程（check函数的作用就是判断将这个课程作为前置课程的课程是否还有其他的前置课程）
7. 如果可以，就接着对这个课程执行find函数
8. 最后栈中的所有值就是拓扑排序的倒序
9. 如果栈中元素等于所有课程数，就可以完全选择，不等于就不行。

class Solution {
    public Stack<Integer>stack=new Stack<Integer>();
    public boolean check(int[][]graph,int x,int[]visited){
        boolean z=true;
        for(int i=0;i<graph.length;i++){
            if(graph[i][x]==1&&visited[i]==0){
                //如果这个点还需要其他入度说明这个点不能选
                z=false;
                break;
            }
        }
        return z;
    }
    public void find(int[][]graph,int[] visited,int i){
        if(visited[i]==1){
            return ;
        }
        visited[i]=1;
        stack.push(i);
        for(int x=0;x<graph.length;x++){
            if(graph[i][x]==1&&check(graph,x,visited)){//说明相连
                find(graph,visited,x);
            }
        }

    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] graph=new int[numCourses][numCourses];
        int[] visited=new int[numCourses];
        int [] beg=new int[numCourses];
        int x,y;
        for(int i=0;i<prerequisites.length;i++){
            x=prerequisites[i][0];//后置
            y=prerequisites[i][1];//前提
            beg[x]=1;//有入度的全部设置为1，方便后面找入度为0的点
            graph[y][x]=1;
        }
        //找个入度为0的起点
        for(int i=0;i<numCourses;i++){
            if(beg[i]==0){
                find(graph,visited,i);
            }
        }
        if(stack.size()==numCourses){
            return true;
        }
        return false;
    }
}

题解思路：
我们使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，我们取出队首的节点 u：

我们将 u 放入答案中；

我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么我们就将 v 放入队列中。

在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

class Solution {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    public void dfs(int u) {
        visited[u] = 1;
        for (int v: edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}