企业官网建设流程全解析

网站未备案会怎么样,旅游电子商务网站建设论文,上海传媒公司名字,三亚网友信奥赛C提高组csp-s之拓扑排序详解 一、拓扑排序基本概念 拓扑排序(Topological Sort)是对有向无环图(DAG)的一种线性排序#xff0c;使得对于图中的每一条有向边(u, v)#xff0c;u在排序中总是位于v的前面。 基本性质#xff1a; 只有有向无环图(DAG)才有拓扑排序一个D…信奥赛C提高组csp-s之拓扑排序详解一、拓扑排序基本概念拓扑排序(Topological Sort)是对有向无环图(DAG)的一种线性排序使得对于图中的每一条有向边(u, v)u在排序中总是位于v的前面。基本性质只有有向无环图(DAG)才有拓扑排序一个DAG可能有多个拓扑排序结果拓扑排序不唯一二、拓扑排序算法实现Kahn算法基于入度算法步骤计算所有节点的入度将所有入度为0的节点加入队列当队列不为空时取出队首节点u加入结果移除u的所有出边即u的邻接节点v的入度减1如果v的入度变为0将v加入队列如果结果包含所有节点则成功否则图中存在环三、研究案例:判环题目描述一个图有n个节点及m条有向边判断该图是否有环。输入格式第一行两个整数n和m表示节点数和边数。接下来m行每行两个整数u和v表示一条有向边从u指向v节点编号从1开始或者0开始这里我们假设从1开始。输出格式如果存在环输出存在环否则输出拓扑排序的结果任意一种即可。数据规模节点数1 ≤ n ≤10 5 10^5105边数0 ≤ m ≤10 5 10^5105输入输出样例样例1无环图输入5 5 1 2 1 3 2 4 3 4 4 5输出1 2 3 4 5样例2有环图输入3 3 1 2 2 3 3 1输出存在环代码实现#includebits/stdc.husingnamespacestd;intn,m;// n: 节点数, m: 边数intmain(){// 输入节点数和边数cinnm;// 邻接表存储图结构g[i]存储节点i指向的所有节点vectorvectorintg(n1);// 入度统计数组d[i]表示节点i的入度指向该节点的边数vectorintd(n1,0);// 读入所有边并构建图for(inti1;im;i){intu,v;cinuv;// 读入一条从u到v的有向边g[u].push_back(v);// 将v添加到u的邻接表中d[v];// v节点的入度增加}queueintq;// 用于拓扑排序的队列存储当前入度为0的节点vectorinttopo;// 存储拓扑排序结果// 将所有初始入度为0的节点加入队列for(inti1;in;i){if(d[i]0){q.push(i);}}// 拓扑排序核心过程Kahn算法while(!q.empty()){intuq.front();// 取出一个入度为0的节点q.pop();topo.push_back(u);// 加入拓扑序列// 遍历当前节点的所有后继节点for(intv:g[u]){d[v]--;// 移除u-v边v的入度减1if(d[v]0){// 如果v的入度变为0q.push(v);// 将v加入队列}}}// 判断是否存在环if(topo.size()!n){// 拓扑序列长度不足n说明存在环cout存在环;}else{// 输出拓扑排序结果for(intnode:topo){coutnode ;}}return0;}功能分析该程序实现了有向图环检测与拓扑排序功能使用经典的Kahn算法图表示与初始化使用邻接表g存储图结构空间效率高适合稀疏图使用入度数组d记录每个节点的入度值拓扑排序过程初始化将所有入度为0的节点加入队列循环处理从队列取出节点加入拓扑序列将该节点的所有后继节点入度减1若减1后入度变为0则加入队列终止条件队列为空环检测拓扑序列长度 n → 无环输出拓扑序列拓扑序列长度 n → 存在环剩余节点形成环算法特性时间复杂度O(nm)每个节点和边各处理一次空间复杂度O(nm)存储图结构和辅助数据结构结果特性拓扑排序结果不唯一与入度为0节点的处理顺序有关算法原理图解样例1无环图 (5节点) 1 → 2 → 4 → 5 1 → 3 → 4 入度初始化: 节点: 1 2 3 4 5 入度: 0 1 1 2 1 处理过程: 1. 节点1入度0 → 加入队列 2. 处理节点1 → 2、3入度减1 → 2入度0入队3入度0入队 3. 处理节点2 → 4入度减1(1) → 不入队 4. 处理节点3 → 4入度减1(0) → 入队 5. 处理节点4 → 5入度减1(0) → 入队 6. 处理节点5 结果: [1,2,3,4,5]或[1,3,2,4,5]样例2有环图 (3节点) 1 → 2 → 3 → 1 入度初始化: 节点: 1 2 3 入度: 1 1 1 处理过程: 所有节点入度0 → 队列始终为空 拓扑序列长度0 ≠ 3 → 存在环四、拓扑排序常见应用场景任务调度确定任务执行的先后顺序课程安排解决课程先修关系问题依赖解析如软件包依赖、编译顺序等死锁检测通过检测环来判断系统是否会出现死锁关键路径在AOE网中计算关键路径各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、csp高频考点知识详解及案例实践CSP信奥赛C之动态规划CSP信奥赛C之标准模板库STL信奥赛C提高组csp-s知识详解及案例实践四、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}