哪家建设网站,网上书城网站开发的结论与不足,做网站打广告图片素材,曹县网站开发作者推荐
视频算法专题
预备知识
本分析针对#xff1a;连通无向图G。
搜索树
节点的父子关系#xff1a;任意 节点的邻接 节点除了已处理 节点#xff0c;都是它的子 节点。 以任意一点为根开始DFS#xff0c;计算所有 节点的父子关系。只保留个子 节点到父 节点形成…作者推荐
视频算法专题
预备知识
本分析针对连通无向图G。
搜索树
节点的父子关系任意 节点的邻接 节点除了已处理 节点都是它的子 节点。 以任意一点为根开始DFS计算所有 节点的父子关系。只保留个子 节点到父 节点形成边形成的树是搜索树。搜索树上的边是树边非树边是回边。 节点级别根节点级别0它的子节点级别1,它的孙节点级别2。 cur子树搜索树中以cur为根的子树。 cur子图dfs(cur) 依次dfs(next各子节点)。整个dfs过程所有cur → \rightarrow → next 形成的边组成的子图简称cur子树。dfs(next)前如果next已编号分配时间戳、访问、处理则不是子节点。
时间戳
计算搜索树上时各节点的时间顺序我的习惯是从0开始。伪代码如下 m_iTime0 DFS( cur) { cur的时间戳是m_iTime。 for(next: cur的未编号邻接点) { dfs(next) } }
若干性质
性质一 搜索树上的两点连通则对应的图一定连通。因为搜索树有的边对应的图都有。 性质二搜索树上假定一个节点n1有m个子节点则删除n1和相关边后有1m个连通区域。各子节点各一个连通区域其它节点一个连通区域简称根子树。根据性质一对应的图最多1m个连通区域。 性质三dfs(c1)前c1到c10的某条路径全部是未访问节点则dfs(c1)时一定会访问c10。 令在这条路径上c1的后继点是c2,c2是c3,c3是c4 ⋯ \cdots ⋯ 第一次处理c1时c1处理完c2的哥哥节点后如果c2未处理则处理c2故c2一定会被处理。 第一次处理c2时c2处理完c3的哥哥节点后如果c3未处理则处理c3故c3一定会被处理。 ⋮ \vdots ⋮ 性质四从两个兄弟子树c1,c2的各选择一个节点c11和c21他们在原图中要么不连通要么任何从c11开始到c21结束的路径一定包括他们的某个公共祖先节点。换种说法c11和c21如果连通一定经过他们的公共祖先。 性质四1:令两个兄弟子树的父亲节点是搜索树的根级别0)假定存在若干组兄弟子树不符合性质四不失一般性假定c1这些组子树中最年长即c1和它的哥哥子树不连通删除它所有的哥哥子树。 因为c1和c11存在不过经过根节点的路径c11和c21存在不经过根节点的路径故c1到c21存在不经过根节点的路径。由于c1是最年长的哥哥节点故dfs(c1)之前只有根节点已处理故c1到c21是全部未处理的路径根据性质三dfs(c1)是会处理c21故c21和c1是一棵子树。与假设矛盾。 性质四2如果某节点cur级别小于等于leve符合性质四。则级别为leve1的节点也符合性质四。 如果c11到c21的某条路径经过cur子树以外的节点c31则必定经过c31和cur的公共祖先必定是c11和c21的公共祖先符合性质四。 如果不经过cur子树以外的节点则删除cur子树外的所有节点。问题就变成性质四1。
判断割点
在一个无向图中如果删除一个节点顶点及相关联的边后图的连通区域分量增加。则此节点是割点。
性质五 dfs(cur) 返回 本次dfs直接或间接dfs各节点的时间戳最小值。dfs(cur) 是节点类型(以cur等于6为例节点类型 一cur的祖先节点部分访问紫色显示。 二cur的祖先节点的哥哥子树访问完成红色显示。 三cur的祖先节点的弟弟子树没有开始访问蓝色显示。 排除next已经访问DFS的返回值分如下几种情况 一只访问了本子树如DFS(3) 等于time[next]。必定和根子树不连通。 二只访问了本子树本子树和cur有两个或以上条边相连如6和12都和2相连。返回值time[cur]。必定和根子树不连通。 三访问了紫,dfs(next)是这些点和cur的最早公共祖先的最小时间戳。如果返回值是time[cur]则说明next子树和cur子树外的节点全部通过cur删除cur后无法和根子树连通。如果小于time[cur]则表示和根子树连通。 四根据性质四访问红蓝节点必定经过紫点而紫点都已经访问故在访问到红蓝点之前DFS会结束。 推论以绿点为起点的边终点要么是绿点要么是紫点。即要么是树边回边非树边一定指向它祖宗。
性质六 假设存在不经过cur存在从next到某个pub的路径则一定可以FDS到。如果此路径经过多个pub 删除第一pub后面的边。因为因为dfs一个和dfs多个pub的结果一样。假设不经过cur性质五证明不经过红色蓝色pub只有一个且在最后其它节点都是绿点。根据性质三最后一个绿点一定会访问访问的时候一定会dfs到此pub。
判断割点的代码
时间复杂度O(n)O(m)。n是顶点数m是边数。每个顶点只会dfs一次每次dfs会循环所有临接点。 【分类讨论】【割点】1568. 使陆地分离的最少天数 如果有多个连通区域同一个连通区域的时间戳是连续的故用m_vRegionFirstTime 记录每个连通区域的最小时间戳。m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后时间戳[left,r)的节点会形成新区域 m_vNodeToTime 各节点的时间戳。
//割点
class CCutPoint
{
public:CCutPoint(const vectorvectorint vNeiB) : m_iSize(vNeiB.size()){m_vNodeToTime.assign(m_iSize, -1);m_vCutNewRegion.resize(m_iSize);for (int i 0; i m_iSize; i){if (-1 m_vNodeToTime[i]){m_vRegionFirstTime.emplace_back(m_iTime);dfs(vNeiB, i, -1);}} }int dfs(const vectorvectorint vNeiB,const int cur, const int parent){int iMinTime m_vNodeToTime[cur] m_iTime;int iRegionCount (-1 ! parent);//根连通区域数量for (const auto next : vNeiB[cur]) {if (-1 ! m_vNodeToTime[next]) {iMinTime min(iMinTime, m_vNodeToTime[next]);continue;}const int childMinTime dfs(vNeiB, next, cur);iMinTime min(iMinTime, childMinTime);if (childMinTime m_vNodeToTime[cur]) {iRegionCount;m_vCutNewRegion[cur].emplace_back(m_vNodeToTime[next], m_iTime);}}if (iRegionCount 2){m_vCutNewRegion[cur].clear();}return iMinTime;}const int m_iSize;const vectorint Time()const { return m_vNodeToTime; }//各节点的时间戳const vectorint RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳vectorbool Cut()const { vectorbool ret;for (int i 0; i m_iSize; i){ret.emplace_back(m_vCutNewRegion[i].size());}return ret; }//是否是割点
protected:vectorint m_vNodeToTime;vectorint m_vRegionFirstTime;vector vectorpairint, int m_vCutNewRegion; //m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后时间戳[left,r)的节点会形成新区域int m_iTime 0;
};判断割点后两点是否连通
增加函数判断割点后两个点是否连通每次调用时间复杂度O(logn)内部用到了二分查找。 【广度优先搜索】【网格】【割点】1263. 推箱子 获取指定割点将所在连通区域分割成若干个子连通区域。时间复杂度O(n)。 【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目
代码
class CCutPoint
{
public:CCutPoint(const vectorvectorint vNeiB) : m_iSize(vNeiB.size()){m_vNodeToTime.assign(m_iSize, -1);m_vCutNewRegion.resize(m_iSize);for (int i 0; i m_iSize; i){if (-1 m_vNodeToTime[i]){m_vRegionFirstTime.emplace_back(m_iTime);dfs(vNeiB, i, -1);}} }int dfs(const vectorvectorint vNeiB,const int cur, const int parent){int iMinTime m_vNodeToTime[cur] m_iTime;int iRegionCount (-1 ! parent);//根连通区域数量for (const auto next : vNeiB[cur]) {if (-1 ! m_vNodeToTime[next]) {iMinTime min(iMinTime, m_vNodeToTime[next]);continue;}const int childMinTime dfs(vNeiB, next, cur);iMinTime min(iMinTime, childMinTime);if (childMinTime m_vNodeToTime[cur]) {iRegionCount;m_vCutNewRegion[cur].emplace_back(m_vNodeToTime[next], m_iTime);}}if (iRegionCount 2){m_vCutNewRegion[cur].clear();}return iMinTime;}const int m_iSize;const vectorint Time()const { return m_vNodeToTime; }//各节点的时间戳const vectorint RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳vectorbool Cut()const { vectorbool ret;for (int i 0; i m_iSize; i){ret.emplace_back(m_vCutNewRegion[i].size());}return ret; }//const vector vectorpairint, int NewRegion()const { return m_vCutNewRegion; };
protected:vectorint m_vNodeToTime;vectorint m_vRegionFirstTime;vector vectorpairint, int m_vCutNewRegion; //m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后时间戳[left,r)的节点会形成新区域int m_iTime 0;
};class CConnectAfterCutPoint
{
public:CConnectAfterCutPoint(const vectorvectorint vNeiB) :m_ct(vNeiB){m_vTimeToNode.resize(m_ct.m_iSize);m_vNodeToRegion.resize(m_ct.m_iSize);for (int iNode 0; iNode m_ct.m_iSize; iNode){m_vTimeToNode[m_ct.Time()[iNode]] iNode;}for (int iTime 0,iRegion 0; iTime m_ct.m_iSize; iTime){if ((iRegion m_ct.RegionFirstTime().size()) (m_ct.RegionFirstTime()[iRegion] iTime)){iRegion;}m_vNodeToRegion[m_vTimeToNode[iTime]] (iRegion - 1);}}bool Connect(int src, int dest, int iCut)const{if (m_vNodeToRegion[src] ! m_vNodeToRegion[dest]){return false;//不在一个连通区域}if (0 m_ct.NewRegion()[iCut].size()){//不是割点return true;}const int r1 GetCutRegion(iCut, src);const int r2 GetCutRegion(iCut, dest);return r1 r2;}vectorvectorint GetSubRegionOfCut(const int iCut)const{//删除iCut及和它相连的边后iCut所在的区域会分成几个区域父节点一个区域、各子节点 一个区域//父节点所在区域可能为空如果iCut所在的连通区域只有一个节点则返回一个没有节点的 区域。const auto v m_ct.NewRegion()[iCut];vectorint vParen;const int iRegion m_vNodeToRegion[iCut];const int iEndTime (iRegion 1 m_ct.RegionFirstTime().size()) ? m_ct.m_iSize : m_ct.RegionFirstTime()[iRegion1];vectorvectorint vRet; for (int iTime m_ct.RegionFirstTime()[iRegion],j-1; iTime iEndTime; iTime){if (iCut m_vTimeToNode[iTime]){continue;}if ((j 1 v.size()) (v[j 1].first iTime)){j;vRet.emplace_back();}const int iNode m_vTimeToNode[iTime];if ((-1 ! j ) (iTime v[j].first) (iTime v[j].second)){vRet.back().emplace_back(iNode);}else{vParen.emplace_back(iNode);} }vRet.emplace_back();vRet.back().swap(vParen);return vRet;}
protected:int GetCutRegion(int iCut, int iNode)const{const auto v m_ct.NewRegion()[iCut];auto it std::upper_bound(v.begin(), v.end(), m_ct.Time()[iNode], [](int time, const std::pairint, int pr) {return time pr.first; });if (v.begin() it){return v.size();}--it;return (it-second m_ct.Time()[iNode]) ? (it - v.begin()) : v.size();}vectorint m_vTimeToNode;vectorint m_vNodeToRegion;//各节点所在区域const CCutPoint m_ct;
};扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
