首页 > 其他分享 >图-邻接表-leetcode207

图-邻接表-leetcode207

时间:2023-07-05 10:31:42浏览次数:40  
标签:int graph numCourses prerequisites 课程 邻接 boolean leetcode207

你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 

  • 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。

示例 1:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。

示例 2:

输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。

提示:

  • 1 <= numCourses <= 105
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同


思路:构建邻接表,然后用dfs遍历,判断是否有环,注意构建邻接表时的顺序,是谁到谁,这里根据题目是反着来的



//leetcode submit region begin(Prohibit modification and deletion)

class Solution {

    boolean[] onPath;
    boolean[] visited;
    boolean hasCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] list = buildGraph(numCourses, prerequisites);
        onPath = new boolean[numCourses];
        visited = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            traverse(list, i);
        }

        return !hasCycle;

    }

    void traverse(List<Integer>[] graph, int s) {
        if (onPath[s]) {
            hasCycle = true;
        }

        if (hasCycle || visited[s]) {
            return;
        }


        onPath[s] = true;
        visited[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        onPath[s] = false;

    }


    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new LinkedList[numCourses];
//        Arrays.fill(graph, new LinkedList<Integer>());

        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }

        for (int[] prereq : prerequisites) {
            int start = prereq[1];
            int end = prereq[0];
            graph[start].add(end);
        }

        return graph;
    }


}


//leetcode submit region end(Prohibit modification and deletion)


标签:int,graph,numCourses,prerequisites,课程,邻接,boolean,leetcode207
From: https://blog.51cto.com/u_12550160/6629503

相关文章

  • 两种常用的存图方法(邻接矩阵和链式前向星)
    今天上午模拟赛的时候,(十分错误地)判断有一道题可以用LCA混点分(然而还不如直接爆搜得分高),在敲那个LCA的代码时突然想起来我好像还没有写过LCA,想了想,是该给我的LCA写点东西了呢。但是!不出意外的,出了亿点点意外,就是我在敲板子题的时候发现经过一年的荒废,我已经完全不会链式前......
  • 图的存储--邻接表
    图的存储--邻接表邻接表表示法顶点:按编号顺序将顶点数据储存在一维数组中;关联同一顶点的边:用线性链表储存.头节点分为数据域和指针域.表节点:邻接点域:存放与vi邻接的顶点在表头数组中的位置.链域:指向下一条边或弧.还可以增加带权值的数据域info无向图的邻接表......
  • 邻接矩阵表示法
    邻接矩阵表示法使用邻接矩阵创建无向图需要一个顶点表和邻接矩阵邻接矩阵的存储结构采用邻接矩阵建立无向网输入总顶点数和总边数。输入点的信息存入顶点表中。初始化化为邻接矩阵,使每个权值初始化为极大值。构造邻接矩阵算法实现在图中查找顶点代码实现#inclu......
  • 图的遍历——DFS, BFS(邻接矩阵,邻接表)——C语言描述
    图的遍历——DFS,BFS(邻接矩阵,邻接表)——C语言描述目录图的遍历——DFS,BFS(邻接矩阵,邻接表)——C语言描述0测试用例框架1图的深度优先遍历(DFS)1.1邻接矩阵(1)数据结构(2)代码(3)测试用例(4)打印结果1.2邻接表(1)数据结构(2)代码(3)测试用例(4)结果2图的广度度优先遍历(BFS)2.1队列(1)数据结构......
  • 数据结构代码整理_基于邻接表的拓扑排序(C++_DFS_BFS_递归)
    目录Chat图解基于栈实现(dfs)基于队列实现(bfs)基于递归实现(dfs)Chat1.代码所属的类在数据结构代码整理_基于邻接表存储结构的有向图的实现(C++)2.拓扑排序的思想就是不断找入度为0的节点并将其输出并标记,标记后与他相连的节点的入度都会减一,不断进行标记直至所有的节点都被输出为止......
  • 数据结构代码整理_基于邻接表存储结构的有向图的实现(C++)
    目录RequirementsDebuggingEnvironmentChatCode1.graph.h2.test.cppRequirements       基于邻接表存储结构实现有向图的典型操作(构造、析构、增加顶点、删除顶点、增加弧、删除弧,查找一个顶点、判空、判满、图中顶点个数、邻接表中指定顶点的第一个邻接顶点、深度优先......
  • 2023-06-10:给定一个由 n 个节点组成的网络,用 n x n 个邻接矩阵 graph 表示 在节点网络
    2023-06-10:给定一个由n个节点组成的网络,用nxn个邻接矩阵graph表示在节点网络中,只有当graph[i][j]=1时,节点i能够直接连接到另一个节点j。一些节点initial最初被恶意软件感染。只要两个节点直接连接,且其中至少一个节点受到恶意软件的感染,那么两个节点都将被恶意软件......
  • 2023-06-10:给定一个由 n 个节点组成的网络,用 n x n 个邻接矩阵 graph 表示 在节点网络
    2023-06-10:给定一个由n个节点组成的网络,用nxn个邻接矩阵graph表示在节点网络中,只有当graph[i][j]=1时,节点i能够直接连接到另一个节点j。一些节点initial最初被恶意软件感染。只要两个节点直接连接,且其中至少一个节点受到恶意软件的感染,那么两个节点都将被恶意......
  • 图的邻接矩阵
    #include<stdio.h>#include<stdlib.h>#defineN20#defineTRUE1#defineFALSE0//访问标志数组intvisited[N];//采用数组定义的队列,用于广度搜索typedefstruct{ intdata[N]; intfront,rear;}SqQueue;//图的邻接矩阵表示typedefstruct{ intvexnum,ar......
  • 描述图的两种数据结构 - 邻接表和邻接矩阵
    图的邻接表和邻接矩阵是两种常用的表示图的数据结构,用于描述图中各个顶点之间的连接关系。图是由一组顶点和一组边组成的数据结构,顶点表示图中的对象,边表示对象之间的关系。邻接表和邻接矩阵都可以有效地表示图的结构,并提供了不同的优势和适用场景。邻接表:邻接表是一种链表的......