企业官网建设流程全解析

python怎么做视频网站,php网站 上传,铁岭做网站哪家好,wordpress搬家后图片不显示割点定义 在无向图G(V,E)中#xff0c;如果一个节点u满足#xff1a;删除u以及与u相关联的所有边后#xff0c;图的连通分量数量增加#xff0c;则称u为割点。 核心思想 Tarjan算法仍然基于深度优先搜索#xff08;DFS#xff09;#xff0c;利用两个关键数组#xff1…割点定义在无向图G(V,E)中如果一个节点u满足删除u以及与u相关联的所有边后图的连通分量数量增加则称u为割点。核心思想Tarjan算法仍然基于深度优先搜索DFS利用两个关键数组dfn[u]节点u的DFS访问顺序时间戳low[u]从u出发不经过DFS树中的父节点能到达的最小dfn值判断割点的条件对于一个节点u有两种情况是割点情况1u不是DFS树的根节点如果存在u的一个子节点v满足low[v] dfn[u]那么u是割点。解释这意味着从v出发在不经过u的情况下无法到达u的祖先节点。移除u后v及其后代将与图的其余部分断开。情况2u是DFS树的根节点如果u有两个或更多个子树在DFS树中那么u是割点。解释作为根节点每个子树之间没有连接除了通过根节点。移除根节点后这些子树将互相断开。模板说明:Run(int _n,const vectorintadj[])传入总点数n和vectorint[]邻接表运行tarjan求割点vectorbool Get()获取cut[]数组cut[i]true则i点是割点templateintNstructCut_vertex{vectorboolcut;//cut[i]true,i是割点intdfn[N],low[N];constvectorint*adj;intn,clk,root;voiddfs_t(intu){dfn[u]low[u]clk;intcnt0;//DFS树的u子树中,去掉u能新增的连通块数for(intto:adj[u]){if(dfn[to]0){dfs_t(to);low[u]min(low[u],low[to]);if(low[to]dfn[u])cnt;}elselow[u]min(low[u],dfn[to]);}if((u!rootcnt1)||cnt2)cut[u]true;elsecut[u]false;}voidRun(int_n,constvectorintadj[]){n_n;clk0;cut.assign(n3,false);fill(low,low3n,0);fill(dfn,dfn3n,0);this-adjadj;for(inti1;in;i)if(dfn[i]0){rooti,dfs_t(i);}}vectorboolGet(){returncut;}};constintmaxn2*1e520;Cut_vertexmaxnT;