企业官网建设流程全解析

php网站开发系统,微商城平台有哪些,设计素材网站上的素材可以商用吗,注册电气师在哪个网站做变更强联通分量(SCC) 有向图中的一个​​极大子图​#xff0c;其中任意两个节点 u 和 v 都​​互相可达​#xff08;即存在 u→v和 v→u的路径#xff09;#xff0c;则这个子图为一个强联通分量 Tarjan 算法基于深度优先搜索#xff08;DFS#xff09;#xff0c;利用 DF…强联通分量(SCC)有向图中的一个​​极大子图​其中任意两个节点u和v都​​互相可达​即存在u→v和v→u的路径则这个子图为一个强联通分量Tarjan 算法基于深度优先搜索DFS利用 DFS 序dfn和low链 来判断一个节点是否是某个强连通分量的“根”即最早被访问的节点。基本定义强连通分量SCC有向图中任意两个节点 u, v 互相可达的最大子图。dfn[u]节点 u 被 DFS 第一次访问的时间戳DFS 序。low[u]从 u 出发通过若干条边可以走树边、后向边、横叉边能到达的所有节点中 最小的 dfn 值。换句话说low[u] min{ dfn[v] | v 从 u 出发可达 }关键性质如果在 DFS 回溯时发现low[u] dfn[u]说明 u 是当前 SCC 的“根”。因为从 u 出发无法回到比 u 更早访问的节点。此时从栈顶到 u 的所有节点构成一个 SCC。栈的作用DFS 过程中将访问的节点压入栈。当找到一个 SCC 的根时从栈中弹出直到 u这些节点就属于同一个 SCC。模板说明void Run(int _n,const vectorintadj[])为传入点的数量vector邻接表数组运行求出所有强联通分量 。·vectorint Get()为获取scc数组即scc[i]为i点属于的强连通分量编号templateintNstructSCC{vectorintscc;vectorintstk;intdfn[N],low[N];constvectorint*adj;intn,clk,tot;//tot:scc数量voiddfs(intu){clk;dfn[u]low[u]clk;stk.push_back(u);for(intto:adj[u]){if(dfn[to]-1){dfs(to);low[u]min(low[u],low[to]);}elseif(scc[to]-1)low[u]min(low[u],dfn[to]);}if(low[u]dfn[u]){intv-1;tot;do{vstk.back();stk.pop_back();scc[v]tot;}while(v!u);}}voidRun(int_n,constvectorintadj[]){n_n;clktot0;stk.clear();fill(low,low3n,-1);fill(dfn,dfn3n,-1);scc.assign(n3,-1);this-adjadj;for(inti1;in;i)if(scc[i]-1)dfs(i);}vectorintGet(){returnscc;}};使用示例templateintNstructSCC{vectorintscc;vectorintstk;intdfn[N],low[N];constvectorint*adj;intn,clk,tot;//tot:scc数量voiddfs(intu){clk;dfn[u]low[u]clk;stk.push_back(u);for(intto:adj[u]){if(dfn[to]-1){dfs(to);low[u]min(low[u],low[to]);}elseif(scc[to]-1)low[u]min(low[u],dfn[to]);}if(low[u]dfn[u]){intv-1;tot;do{vstk.back();stk.pop_back();scc[v]tot;}while(v!u);}}voidRun(int_n,constvectorintadj[]){n_n;clktot0;stk.clear();fill(low,low1n,-1);fill(dfn,dfn1n,-1);scc.assign(n3,-1);this-adjadj;for(inti1;in;i)if(scc[i]-1)dfs(i);}vectorintGet(){returnscc;}};constintmaxn2*1e520;SCCmaxnT;vectorinte[maxn];intmain(){intn,m;//n个点m条边for(inti1;im;i){//输入m条边intu,v;cinuv;e[u].push_back(v);}T.Run(n,e);//跑tarjanvectorintsccT.Get();//获取scc数组scc[i]i点属于的强连通分量编号