企业官网建设流程全解析

滨州网站建设求职简历,网站开发的优势,公众号开发者中心,网站建设 后台信奥赛C提高组csp-s之强连通分量详解 1、核心概念 强连通分量#xff08;SCC#xff09;#xff1a;有向图中满足以下条件的最大子图#xff1a;任意两个节点互相可达#xff08;存在双向路径#xff09; 关键性质#xff1a; 每个节点属于且仅属于一个SCCSCC之间形成…信奥赛C提高组csp-s之强连通分量详解1、核心概念强连通分量SCC有向图中满足以下条件的最大子图任意两个节点互相可达存在双向路径关键性质每个节点属于且仅属于一个SCCSCC之间形成有向无环图DAG是图分解的基本结构用于简化图分析2、Tarjan算法原理时间戳DFS遍历时给节点分配唯一编号dfn追溯值low记录节点能访问到的最早时间戳栈维护存储当前搜索路径上的节点分量判定当dfn[u] low[u]时栈顶到u的节点构成SCC算法流程初始化时间戳计数器DFS遍历未访问节点更新当前节点low值通过回边或子树发现根节点时弹出栈中节点形成SCC研究案例求解强连通分量题目描述给定有向图求出所有强连通分量并按以下规则输出每个分量内节点升序排列分量按最小节点编号升序排列输入格式第1行节点数n 边数m1≤n≤10000, 1≤m≤100000第2~m1行每条边的起点u和终点v输出格式每行一个强连通分量的节点空格分隔行按分量最小节点编号升序排列样例输入6 7 1 2 2 3 3 1 2 4 4 5 5 6 6 4样例输出1 2 3 4 5 6数据规模节点数10 4 10^4104边数10 5 10^5105时间限制1s代码实现#includebits/stdc.husingnamespacestd;constintN10010;// 最大节点数vectorintgraph[N];// 邻接表存图intdfn[N];// 访问时间戳intlow[N];// 最早可回溯时间戳boolinStack[N];// 节点在栈中标记stackintstk;// DFS栈inttimestamp;// 全局时间戳vectorvectorintsccList;// 存储所有SCC// Tarjan算法核心voidtarjan(intu){dfn[u]low[u]timestamp;// 初始化时间戳stk.push(u);inStack[u]true;// 遍历所有邻接点for(intv:graph[u]){if(!dfn[v]){// 未访问节点tarjan(v);low[u]min(low[u],low[v]);// 通过子树更新}elseif(inStack[v]){// 已访问且在栈中回边low[u]min(low[u],dfn[v]);// 更新追溯值}}// 发现SCC根节点if(dfn[u]low[u]){vectorintscc;while(true){inttopstk.top();stk.pop();inStack[top]false;scc.push_back(top);if(topu)break;// 弹出至当前节点}sccList.push_back(scc);}}boolcmp(vectorinta,vectorintb){returna[0]b[0];}intmain(){// 读入数据intn,m;cinnm;// 建图for(inti0;im;i){intu,v;cinuv;graph[u].push_back(v);}// 初始化memset(dfn,0,sizeof(dfn));memset(inStack,false,sizeof(inStack));timestamp0;// 执行Tarjan算法for(inti1;in;i){if(!dfn[i])tarjan(i);// 未访问节点}// 处理输出for(autoscc:sccList){sort(scc.begin(),scc.end());// 分量内排序}// 按分量最小节点排序sort(sccList.begin(),sccList.end(),cmp);// 输出结果for(autoscc:sccList){for(inti0;iscc.size();i){coutscc[i] ;}coutendl;}return0;}代码解析数据结构dfn[]记录DFS访问顺序low[]记录通过回边能访问到的最早时间戳inStack[]标记节点是否在DFS栈中stk维护当前DFS路径Tarjan核心步骤if(!dfn[v]){tarjan(v);low[u]min(low[u],low[v]);// 情况1v是子树}elseif(inStack[v]){// 情况2v是祖先节点low[u]min(low[u],dfn[v]);}SCC识别if(dfn[u]low[u]){// 发现SCC根节点// 弹出栈中节点直到uwhile(stk.top()!u){// 弹出节点加入当前SCC}// 将完整SCC加入结果集}复杂度分析时间复杂度O(nm) - 每个节点和边只访问一次空间复杂度O(n) - 栈和辅助数组空间算法应用图化简将SCC缩为超级节点得到DAG环路检测SCC内部存在环路依赖分析编译器优化、任务调度网络分析社交网络中的紧密社群发现各种学习资料助力大家一站式学习和提升#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;}