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}{n−1个非根节点最终目的地是根节点，说明这些定点的出度至少为1。总共n−1条边。→{根节点出度为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 。必要条件无需证明环是：B→A→B。
现在证明充分条件：
由于是环，所以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不是冲突边。
