【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II

2024-02-19 09:12

本文主要是介绍【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode685. 冗余连接 II

在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。
输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1 到 n)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。
返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。
示例 1:

输入:edges = [[1,2],[1,3],[2,3]]
输出:[2,3]
示例 2:
输入:edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出:[4,1]
提示:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n

预备知识

有向图并集查找使用的2个前提:

前提一:所有的点出度为1或为0。
前提二:无环。
以当前节点为起点的最长路径终点,简称最长终点。如:两条边 A B → \overrightarrow{AB} AB B C → \overrightarrow{BC} BC ,A的最长终点是C。

有向树性质

性质一:任意节点都能访问自己所有后代,且不能访问自己后代之外的节点。
性质二:如果删除的边不是指向某节点的祖先,则根节点一定能访问此节点。

暴力解法

枚举删除的边,时间复杂度O(n);判断余下的边是否是有根树,时间复杂度O(n^n)。

深度优先判断有根树

前提三该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。 ⟺ \iff 只有一个节点的入度为0,此节点为根。其它节点入度为1。
前提四该树只有一个根节点,所有其他节点都是该根节点的后继。 ⟺ \iff 根节点可以访问所有的节点。通过一条边直接访问的节点是根节点的后继。通过两条边访问的节点是后继的后继 ⋯ \cdots
如果有环一定不行,n-1条边,如果有重复节点则无法访问n-1个新节点。所以访问了重复的节点直接返回。

核心代码

class Solution {
public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {m_c = edges.size();for (int i = m_c-1 ; i >=0 ;i--){vector<vector<int>> vNeiBo(m_c);for (int j = 0; j < m_c; j++){if (j != i){vNeiBo[edges[j][0] - 1].emplace_back(edges[j][1] - 1);}}if (Is(vNeiBo)){				return edges[i];}}return {};}bool Is(const vector<vector<int>>& vNeiBo)const{vector<int> vInDeg(m_c);for (const auto& v : vNeiBo){for (const auto& to : v){vInDeg[to]++;}			}for (int i = 0; i < m_c; i++){if (0 == vInDeg[i]){vector<int> vVis(m_c);DFS(vVis, vNeiBo, i);return m_c == std::accumulate(vVis.begin(), vVis.end(), 0);}}return false;}void DFS(vector<int>& vVis, const vector<vector<int>>& vNeiBo,int cur)const{if (vVis[cur]){return;}vVis[cur] = 1;for (const auto& next : vNeiBo[cur]){DFS(vVis, vNeiBo, next);}}int m_c;};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<vector<int>> edges;{Solution sln;edges = { {5,2},{5,1},{3,1},{3,4},{3,5} };auto res = sln.findRedundantDirectedConnection(edges);Assert({ 3,1 }, res);}{Solution sln;edges = { {1, 2}, { 2,3 }, { 3,1 }, { 4,1 } };auto res = sln.findRedundantDirectedConnection(edges);Assert({ 3,1 }, res);}{Solution sln;edges = { {1,2},{1,3},{2,3} };auto res = sln.findRedundantDirectedConnection(edges);Assert({ 2,3 }, res);}{Solution sln;edges = { {1,2},{2,3},{3,4},{4,1},{1,5} };auto res = sln.findRedundantDirectedConnection(edges);Assert({ 4,1 }, res);}{Solution sln;edges = { {2,1},{3,1},{4,2},{1,4} };auto res = sln.findRedundantDirectedConnection(edges);Assert({ 2,1 }, res);}{Solution sln;edges = { {4,2},{1,5},{5,2},{5,3},{2,4} }		;auto res = sln.findRedundantDirectedConnection(edges);Assert({ 4,2 }, res);}
}

并集查找

所有边反向,即:根节出度为0,其它节点出度为1。所有节点的最长终点是都是根节点。即判定一:所有节点的最终节点相同。
有向树是判断一,无需证明。下面来证明判断一一定是有向树,判定一符合前提四无需证明,只需证明判定一符合前提三。
{ n − 1 个非根节点最终目的地是根节点,说明这些定点的出度至少为 1 。 总共 n − 1 条边。 → { 根节点出度为 0 其它节点出度为 1 \begin{cases} n-1个非根节点最终目的地是根节点,说明这些定点的出度至少为1。\\ 总共n-1条边。\\ \end{cases}\rightarrow \begin{cases}根节点出度为0\\ 其它节点出度为1 \end{cases} {n1个非根节点最终目的地是根节点,说明这些定点的出度至少为1总共n1条边。{根节点出度为0其它节点出度为1

简化

n-1条边,如果无环,则说明访问了n-1个新节点。且只有一个连通区域,否则顶点更多。故:
无环没有出度为2的定点 ⟺ \iff 有向树

代码

class CUnionFindDirect
{
public:CUnionFindDirect(int iSize){m_vRoot.resize(iSize);iota(m_vRoot.begin(), m_vRoot.end(), 0);}void Connect(bool& bConflic, bool& bCyc, int iFrom, int iTo){bConflic = bCyc = false;if (iFrom != m_vRoot[iFrom]){bConflic = true;}Fresh(iTo);if (m_vRoot[iTo] == iFrom){bCyc = true;}if (bConflic || bCyc){return;}m_vRoot[iFrom] = m_vRoot[iTo];}
private:int Fresh(int iNode){if (m_vRoot[iNode] == iNode){return iNode;}return m_vRoot[iNode] = Fresh(m_vRoot[iNode]);}vector<int> m_vRoot;
};class Solution {
public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {m_c = edges.size();for (int i = m_c-1 ; i >=0 ;i--){			if (Is(edges,i)){				return edges[i];}}return {};}bool Is(const vector<vector<int>>& edges,int i )const{CUnionFindDirect uf(m_c);for (int j = 0; j < m_c; j++){if (j != i){bool b2 = false, bCyc = false;uf.Connect(b2,bCyc,edges[j][1] - 1, edges[j][0] - 1);if (b2 || bCyc){return false;}}}return true;}int m_c;};

特殊情况

如果有环,计算最长终点,可能会死循环。所以要提前判断。有环 ⟺ \iff B的最长终点是A,发现新边 A B → \overrightarrow{AB} AB
必要条件无需证明环是: B → A → B 。 必要条件无需证明环是:B \rightarrow A \rightarrow B 。 必要条件无需证明环是:BAB
现在证明充分条件:
由于是环,所以B一定能到A,假定增加新边 A B → \overrightarrow{AB} AB 前,B的最长终点是C,那么A能访问C,也就是A出度至少为1。加上 A B → \overrightarrow{AB} AB 出度就成了2。和前提三矛盾。

优化

有向森林B的父节点是C,增加的边 A B → \overrightarrow{AB} AB 。有以下两种情况:
一,无环。如果B不是A的祖先,则B无法访问A,增加新边后,就无法形成环。存在入度为2的顶点
1.1,和森林的某边重合。删除任意一边。
在这里插入图片描述

1.2,前向边,A是祖先,B是后代(A能访问B)。
在这里插入图片描述
如果先发现AB,后发现CB则是横叉边。
1.3,横叉变。A和B都无法到达他们的公共祖先,所以不会有环。
在这里插入图片描述
如果先发现AB,后发现CB则是前向边。
总结: 根据性质二,B不会是A祖先,所以1.2和1.3删除CB不会影响根节点访问A。

二,后向边,B是祖先,A是后代,B能访问A。增加新边后,A能访问B。形成了环。
2.1,如果B是根节点,则这个环上所有节点都能访问B,也就是能访问所有节点。删除任意一边后,会形成新树。不存在入度为2的顶点
在这里插入图片描述

,2.2 如果B不是根节点。不包括 C B → \overrightarrow{CB} CB A B → \overrightarrow{AB} AB 如果C是根节点的后代,则删除 A B → \overrightarrow{AB} AB 可以形成新树 。如果A是根节点的后代,则删除 C B → \overrightarrow{CB} CB ,可形成新树 。存在入度为2的顶点

在这里插入图片描述

无论是发现环,还是发现入度为2,还是同时发现环和入度为2,都只能删除折线。
处理方法一: { 删除 C B → 不通过 C B → ,根节点能到达 A 。 删除 A B → 不通过 A B → ,根节点能到达 C 。 处理方法一:\begin{cases} 删除\overrightarrow{CB} & 不通过\overrightarrow{CB},根节点能到达A。\\ 删除\overrightarrow{AB} &不通过\overrightarrow{AB},根节点能到达C。\\ \end{cases} 处理方法一:{删除CB 删除AB 不通过CB ,根节点能到达A不通过AB ,根节点能到达C

总结,5种情况合并两种:
{ 删除环中任意一边(最后一边) 不存在入度为 2 的定点 处理方法一 o t h e r \begin{cases} 删除环中任意一边(最后一边) & 不存在入度为2的定点 \\ 处理方法一 & other \\ \end{cases} {删除环中任意一边(最后一边)处理方法一不存在入度为2的定点other

代码

class CUnionFindDirect
{
public:CUnionFindDirect(int iSize){m_vRoot.resize(iSize);iota(m_vRoot.begin(), m_vRoot.end(), 0);}void Connect(bool& bConflic, bool& bCyc, int iFrom, int iTo){bConflic = bCyc = false;if (iFrom != m_vRoot[iFrom]){bConflic = true;}Fresh(iTo);if (m_vRoot[iTo] == iFrom){bCyc = true;}if (bConflic || bCyc){return;}m_vRoot[iFrom] = m_vRoot[iTo];}int GetMaxDest(int iFrom){Fresh(iFrom);return m_vRoot[iFrom];}	
private:int Fresh(int iNode){if (m_vRoot[iNode] == iNode){return iNode;}return m_vRoot[iNode] = Fresh(m_vRoot[iNode]);}vector<int> m_vRoot;
};class Solution {
public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {m_c = edges.size();vector<int> vParent(m_c, -1);int iParentOld = -1;for (int j = 0; j < m_c; j++){if (vParent[edges[j][1] - 1] >= 0){iParentOld = vParent[edges[j][1] - 1];}vParent[edges[j][1] - 1] = edges[j][0] - 1;}const int root = std::find(vParent.begin(), vParent.end(), -1) - vParent.begin();CUnionFindDirect uf(m_c);		int iCyc = -1;int i2 = -1;for (int j = 0; j < m_c; j++){bool b2 = false, bCyc = false;uf.Connect(b2, bCyc, edges[j][1] - 1, edges[j][0] - 1);if (b2){i2 = j;}if (bCyc){iCyc = j ;}}if (-1 != i2){const int dest = uf.GetMaxDest(edges[i2][1] - 1);return (root == dest) ? edges[i2] : vector<int>{ iParentOld + 1, edges[i2][1] };}return edges[iCyc];}int m_c;
};

注意

一,所有边都加到并集查找才判断最长终点。
二,由于冲突边和环边会忽略。所以可能出现 忽略环边时,让冲突边也消失。碰巧可以按环处理。
在这里插入图片描述
BA和CD已经发现,CB未发现。发现AB是环边,忽略。由于AB被忽略,所以CB不是冲突边。

娱乐性优化

情况2.2进一步分析,无论何种发现顺序都是删除环冲突边:
2.2.1,同时发现环边和冲突边。环冲突边最后发现。删除冲突边。
2.2.2 先发现环边,环边是冲突边。无法发先冲突边。删除环边。
2.2.3先发现环边,环边不是冲突边。能发现冲突边。删除另外一条冲突边。
2.2.4 先发现冲突边,忽略冲突环边,无法发现环。删除冲突边。
2.2.5 先发现冲突边,忽略非环冲突边,能发现环。删除另外一条冲突边。
总结: { 删除冲突边 发现冲突边未发现环边 1 , 2.2.4 删除环边 发现环边未发现冲突边 2.1 , 2.22 删除冲突边(环边 ) 冲突边就是环边 2.2.1 删除另外一条冲突边 发现冲突边和环边两者不等 2.2.3 , 2.25 总结:\begin{cases} 删除冲突边 & 发现冲突边未发现环边 & 1,2.2.4 \\ 删除环边 & 发现环边未发现冲突边 &2.1, 2.22 \\ 删除冲突边(环边) & 冲突边就是环边 & 2.2.1 \\ 删除另外一条冲突边 & 发现冲突边和环边两者不等 & 2.2.3,2.25\\ \end{cases} 总结: 删除冲突边删除环边删除冲突边(环边)删除另外一条冲突边发现冲突边未发现环边发现环边未发现冲突边冲突边就是环边发现冲突边和环边两者不等1,2.2.42.1,2.222.2.12.2.3,2.25

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/724216

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

W外链微信推广短连接怎么做?

制作微信推广链接的难点分析 一、内容创作难度 制作微信推广链接时,首先需要创作有吸引力的内容。这不仅要求内容本身有趣、有价值,还要能够激起人们的分享欲望。对于许多企业和个人来说,尤其是那些缺乏创意和写作能力的人来说,这是制作微信推广链接的一大难点。 二、精准定位难度 微信用户群体庞大,不同用户的需求和兴趣各异。因此,制作推广链接时需要精准定位目标受众,以便更有效地吸引他们点击并分享链接

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

防近视护眼台灯什么牌子好?五款防近视效果好的护眼台灯推荐

在家里,灯具是属于离不开的家具,每个大大小小的地方都需要的照亮,所以一盏好灯是必不可少的,每个发挥着作用。而护眼台灯就起了一个保护眼睛,预防近视的作用。可以保护我们在学习,阅读的时候提供一个合适的光线环境,保护我们的眼睛。防近视护眼台灯什么牌子好?那我们怎么选择一个优秀的护眼台灯也是很重要,才能起到最大的护眼效果。下面五款防近视效果好的护眼台灯推荐: 一:六个推荐防近视效果好的护眼台灯的

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

智能交通(二)——Spinger特刊推荐

特刊征稿 01  期刊名称: Autonomous Intelligent Systems  特刊名称: Understanding the Policy Shift  with the Digital Twins in Smart  Transportation and Mobility 截止时间: 开放提交:2024年1月20日 提交截止日