题目描述
在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。每一个节点只有一个父节点,除了根节点没有父节点。
输入一个有向图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。
结果图是一个以边
组成的二维数组。 每一个边 的元素是一对 [u, v]
,用以表示有向图中连接顶点 u
and v
和顶点的边,其中父节点 u
是子节点 v
的一个父节点。
返回一条能删除的边,使得剩下的图是有N个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。
示例 1:
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
1
/ \
v v
2-->3
示例 2:
输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
^ |
| v
4 <- 3
注意
- 二维数组大小的在3到1000范围内。
- 二维数组中的每个整数在1到N之间,其中 N 是二维数组的大小。
算法1
(并查集+分情况讨论) $O(n)$
对于多余的边,只会有三种情况:
-
多余的边构成了一个有向环。如图所示:
-
多余的边构成了一个入度为2的点。如图所示:
-
多余的边既构成了环又构成了入度为2的点。如图所示:
前面两种情况都很好考虑,我们直接让当前遇到的非法边失效就好,关键在于第三种情况,即既有环又有一个入度为2的点,我们当前遇到的非法边可能不是答案,比如我们遇到的非法边可能是1号点右边的边,但其实答案是之前加入的1号点左边的边。下面我们分情况来讨论:
我们从前往后遍历每条边,用并查集来维护点之间的关系,当我们发现加入一条边会构成矛盾时:
- 如果构成了环,我们将这条边记录下来,并且让这条边失效。
- 如果构成了入度为2的点,我们将这条边记录下来并让它失效,我们再另外记录这条边终点的另外一条边。换句话说就是把导致入度为2的两条边都记录下来。
所以当我们已经遇到了一条非法边并删去它后,我们又遇到了一条非法边,说明我们之前删的边是错误的:
- 如果之前遇到了环,说明之前删去的边不是构成入度为2的两条边之一,那我们应该删去当前非法边终点的另一条边。比如我们按照 $4 \rightarrow 2, 2 \rightarrow 1, 1 \rightarrow 4(构成了环,删去), 3 \rightarrow 1$ 的顺序,当我们又遇到了非法边 $3 \rightarrow 1$ 时,我们知道答案应该是 $2 \rightarrow 1$。
- 如果之前遇到了入度为2的点,说明我们应该删去构成入度为2的两条边的另一条边。比如我们按照 $2 \rightarrow 1, 3 \rightarrow 1(构成了入度为2的点,删去), 1 \rightarrow 4, 4 \rightarrow 2$ 的顺序,当我们又遇到了非法边 $4 \rightarrow 2$ 时,我们知道答案应该是 $2 \rightarrow 1$。
C++ 代码
class Solution {
public:
vector<int> father, p;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
for (int i = 0; i <= n; i ++ )
{
p.push_back(i);
father.push_back(0);
}
vector<int> res;
for (int i = 0; i < n; i ++ )
{
int a = edges[i][0], b = edges[i][1];
int fa = find(a), fb = find(b);
if (father[b] != 0) // 构成了入度为2的点
{
if (res.size()) return {father[b], b};
else res = {a, b, father[b], b};
}
else if (fa == fb) // 构成了环
{
if (res.size()) return {res[2], res[3]};
else res = {a, b};
}
else
{
father[b] = a;
p[b] = a;
}
}
return {res[0], res[1]};
}
};
算法2
(并查集+预处理) $O(n)$
我们可以观察到如果有入度为2的点,那么答案一定在这两条边之内,只是我们不确定应该删去哪一条。
其实我们可以先统计出有没有入度为2的点,如果没有那做法就和 684. Redundant Connection 一样,用并查集找环就可以了。如果有的话,那我们就把终点是该点的两条边给删去,这样剩下的边一定都是合法的,然后我们遍历剩下的边做并查集,之后我们把这两条边加进去,返回出现矛盾的边即可。
C++ 代码
class Solution {
public:
vector<int> p;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> cnt(n + 1, 0);
int k = -1;
for (auto& e : edges)
if ( ++ cnt[e[1]] == 2) k = e[1];
p = vector<int>(n + 1, 0);
for (int i = 1; i <= n; i ++ ) p[i] = i;
vector<int> tmp;
for (auto& e : edges)
{
// 将构成入度为2的两条边都删去,这里记录的是边的起点
if (e[1] == k)
{
tmp.push_back(e[0]);
continue;
}
int a = find(e[0]), b = find(e[1]);
if (a == b) return {e[0], e[1]}; // 有环可以直接确定答案
p[a] = b;
}
int a = find(tmp[0]), b = find(k);
if (a == b) return {tmp[0], k}; // 加入第一条边时出现了矛盾,即构成了环
return {tmp[1], k};
}
};
方法2写的太好了!respect
并查集没有按秩合并复杂度是 $\log n$
是的,在只有路径压缩的情况下对大小为n的并查集做m次union或find操作的复杂度为$O(n + m\log n)$
方法2太优美了!
这个
father
数组是干嘛的?father
数组记录每条边的起点,比如对于边[u, v]
,father[v] = u
。