#Problem

#⭐️⭐️⭐️⭐️⭐️

和LeetCode 684差不多, 只是这道题变成了directed graph. 题目是说有一个tree with directed graph, 现在这个tree多了一条redundant edge, 把它找出来.

#Mistake

首先第一反应是directed graph和undirected graph有什么区别? 不能用union-find一样做么?

答案显然是不能的,不然也不会是medium和hard的区别了.

考虑一下这个图:

[[2,1],[3,1],[4,2],[1,4]]

很明显答案应该在[2,1]或者[3,1]里面, 但是直接用union-find会得到[1,4]

#Solution

正确的做法是要考虑每个结点的indegreeoutdegree. 要成为一棵树, 每个结点的degree必须满足以下几个条件:

  1. 有且只有一个结点的indegree为0, 就是root.
  2. 叶子结点的outdegree必须为0.
  3. 中间结点的indegree和outdegree必须都等于1.

那么首先要做的就是遍历一遍graph来计算indegree和outdegree, 会得到两种结果, 一定要注意会有两种结果:

  1. 有一个结点的indegree为0, 肯定是root. 还有一个结点的indegree为2,因为redundant edge.
    • 这种结果可能有cycle也可能没有cycle!!!
  2. 所有结点的indegree都为1. 这种情况下, redundant edge肯定是指向了root, 形成了cycle.

得到indegree和outdegree之后就要开始找redundant edge了.

  • 首先看一下第二种结果, 第二种结果算一个edge case, 虽然一开始很难想到, 但是处理起来还是比较方便. 因为这种情况下redundant edge肯定是指向了root, 所以我们只要找到root就可以了. root要满足的条件是indegree为0而且outdegree不能为0.

    • 因为题目是要求如果有多条redundant edge, 返回最后一条. 那么就从数组最后开始遍历, 看去掉每条边更新后的indegree和outdegree就能找到redundant edge.
    • 要注意的不只是要找root, 一开始写的算法只关注了indegree, 想着只要更新后的indegree为0的, 就是redundant edge. 但是这样是不对的!!!如果当前的edge是一条指向叶子结点的边, 更新后的indegree和outdegree都为0,但如果删除这条边,这个叶子结点就被孤立了!
  • 第一种情况比较复杂. 但是仔细想一下出现这种情况的原因是因为有2条edge同时指向了同一个结点(这就是要找一个结点indegree为2的原因). 那么redundant edge只有可能是这2条edges之中的一条.

    • 至于怎么确定是哪一条最简单的方法就分别去掉之后做一个dfs就好了.
    • 这时候我们已经知道哪个结点的indegree为0, 就是root. 从root做dfs要是不能把所有结点都遍历到, 那肯定就是redundant edge
    • 因为最多只有2个candidates, 所以最多也只会做两次dfs.

#Performance

自己的算法时间复杂度虽然在数量级上是最优的. 但是constant有一些高.

  1. 计算indegree和outdegree需要O(E + V)
  2. 找出candidates或者root需要O(V)
  3. 确定最后的candidate需要O(2 * (E + V)) 或者 O(E)

随意如果N = V = E, 那么worst case需要 O(7 * N) time.

#Optimization

https://leetcode.com/problems/redundant-connection-ii/discuss/108045/C++Java-Union-Find-with-explanation-O(n)

参考别人的解法之后发现基本思路是一致的,但是可以优化的地方有很多:

  1. 不用算完indegree和outdegree之后再去找candidates. 或者根本不用算degree就可以遍历一遍直接找出candidates. (自己的解法需要遍历2遍)
  2. 不需要两种结果分开处理, 利用union-find就可以解决所有情况.
  3. 整个算法只需要上面2步即可完成.

因为上面提到的第二种结果必定存在cycle, 所以即使在第一步没有找到candidates, 也可以通过第二步union-find来找到环.

而如果第一步找到了candidates, 说明是第一种结果, 第一种结果可能有cycle也可能没有Cycle!

  • 在没有cycle的情况下,说明没有backward edge. 也就可以肯定的是redundant edge的source和destination是在从root出发的两条不同path中,如果是source和destination在同一条path中,那显然是cycle.
  • 在这种情况下两条candidates去掉任意一条都是可以的. 比如下面两个例子:

  • 根据上面的分析, 那么只剩下有cycle的情况了, 用union-find把cycle找出来即可

#Code

#Solution #1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
// Tree with directed graph will only have ONE vertex has 0 indegree and non-one outdegree.
// Other vertices will have exactly 1 indegree and 1 or 0 outdegree.
public int[] findRedundantDirectedConnection(int[][] edges) {
// Tree will have n - 1 edges, and there is one more redundant edge.
// So the number of vertices is the length of input edges
final int n = edges.length;
int[] indegree = new int[n + 1];
int[] outdegree = new int[n + 1];
final Map<Integer, Set<Integer>> adjList = new HashMap<>();
for (int i = 1; i <= n; i++) {
adjList.put(i, new HashSet<>());
}
int edgeTo = -1;
for (final int[] edge : edges) {
outdegree[edge[0]]++;
indegree[edge[1]]++;
if (indegree[edge[1]] > 1) {
edgeTo = edge[1];
}
adjList.get(edge[0]).add(edge[1]);
}
int[] res = null;
if (edgeTo != -1) {
int root = -1;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) root = i;
}
for (int i = n - 1; i >= 0; i--) {
if (edges[i][1] == edgeTo) {
if (tryDeleteEdge(edges[i][0], edges[i][1], root, adjList)) {
res = edges[i];
break;
}
}
}
} else {
for (int i = n - 1; i >= 0; i--) {
int v = edges[i][0];
int w = edges[i][1];
if (indegree[v] - 1 == 0 && outdegree[w] - 1 == 0) {
continue;
} else if (indegree[v] - 1 == 0) {
res = edges[i];
}
}
}
return res;
}
private boolean tryDeleteEdge(final int v, final int w, final int root, final Map<Integer, Set<Integer>> adjList) {
final Set<Integer> visited = new HashSet<>();
dfs(root, v, w, adjList, visited);
return visited.size() == adjList.size();
}
private void dfs(int v, int from, int to, Map<Integer, Set<Integer>> adjList, Set<Integer> visited) {
visited.add(v);
for (final int adj : adjList.get(v)) {
if (!visited.contains(adj) && (v != from || adj != to)) {
dfs(adj, from, to, adjList, visited);
}
}
}
}
#Solution #2 with Optimization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
final int n = edges.length;
final int[] parent = new int[n + 1];
final int[] candA = new int[2];
final int[] candB = new int[2];
for (final int[] edge : edges) {
if (parent[edge[1]] != 0) {
candA[0] = parent[edge[1]];
candA[1] = edge[1];
candB[0] = edge[0];
candB[1] = edge[1];
// Mark the second edge as candidate. (This condition will be entered ONLY ONCE)
// In this case, it's B!
edge[1] = 0;
} else {
parent[edge[1]] = edge[0];
}
}
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (final int[] edge : edges) {
if (edge[1] == 0) continue;
int rootU = root(parent, edge[0]);
int rootV = root(parent, edge[1]);
// find
if (rootU == rootV) {
return candA[0] == 0 ? edge : candA;
}
// union
parent[edge[1]] = rootU;
}
return candB;
}
private int root(final int[] parent, int v) {
while (parent[v] != v) {
parent[v] = parent[parent[v]];
v = parent[v];
}
return v;
}
}

Comments