西安行业网站制作手机网站怎么搭建

西安行业网站制作,手机网站怎么搭建,网站建设性能指标,个人用云服务器定义 在无向图G(V,E)中#xff0c;如果删除任意一个节点#xff08;及其关联的边#xff09;后#xff0c;子图仍然连通#xff0c;则称这个子图是点连通的。 点双连通分量#xff08;Vertex Biconnected Component, vDCC#xff09;#xff1a;图的极大点连通子图。 重…定义在无向图G(V,E)中如果删除任意一个节点及其关联的边后子图仍然连通则称这个子图是点连通的。点双连通分量Vertex Biconnected Component, vDCC图的极大点连通子图。重要性质点双连通分量内部没有割点不同的点双连通分量之间通过割点连接一个割点可以属于多个点双连通分量点双连通分量和割点一起可以构成块-割点树Tarjan算法求点双连通分量1. 算法核心思想Tarjan算法基于深度优先搜索DFS是求割点算法的扩展。核心思想是在DFS过程中维护一个栈存储当前搜索路径上的节点当发现一个割点时从栈中弹出节点直到当前节点的子节点弹出的节点与割点一起构成一个点双连通分量注意割点不出栈因为它可能属于多个分量2. 算法流程// 核心判断条件if(low[to]dfn[u]){// 发现割点u的一个vDCCtot;// 新增一个点双连通分量intv;do{vstk.top();stk.pop();Dcc[tot].push_back(v);}while(v!to);// 弹出直到子节点toDcc[tot].push_back(u);// 割点u也加入分量}模板说明:void Run(int _n,vectorint adj[])传入总点数nvectorint[]邻接表adj,运行Tarjan求点双联通分量。vectorint Dcc[N]Dcc[i]存了编号为i的vDcc内所有的点.templateintNstructvDCC{intdfn[N],low[N];constvectorint*adj;vectorintstk,cut;vectorintDcc[N];//1~tot,Dcc[i]编号为i的vDcc内的点.inttot;//vDcc数量intn,clk,root;voiddfs(intu){dfn[u]low[u]clk;stk.push_back(u);intcnt0;for(intto:adj[u]){if(dfn[to]0){dfs(to);low[u]min(low[u],low[to]);if(low[to]dfn[u]){cnt;tot;intv;do{vstk.back();stk.pop_back();Dcc[tot].emplace_back(v);}while(v!to);Dcc[tot].emplace_back(u);}}elselow[u]min(low[u],dfn[to]);}if((u!rootcnt1)||cnt2)cut[u]true;if(cnt0uroot)Dcc[tot].pb(u);}voidRun(int_n,vectorintadj[]){n_n;this-adjadj;clktot0;fill(dfn,dfnn3,0);fill(low,lown3,0);stk.clear();cut.assign(n3,false);for(inti0;in3;i)Dcc[i].clear();for(inti1;in;i){if(dfn[i]0){rooti;dfs(i);}}}};constintmaxn2*1e520;vDCCmaxnT;