https://leetcode.com/problems/redundant-connection-ii/
The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array
http://www.cnblogs.com/grandyang/p/8445733.html
X. Union Find
https://zxi.mytechroad.com/blog/graph/leetcode-685-redundant-connection-ii/
http://reeestart.me/2018/03/21/LeetCode-685-Redundant-Connection-II/
http://hehejun.blogspot.com/2017/09/leetcoderedundant-connection-ii.html
和之前题目不一样的是这道题目变成了有向图。那么变为有向图之后，我们对directed tree加上一条边和undirected tree有什么区别呢。可能会有以下三种状况：
https://leetcode.com/problems/redundant-connection-ii/discuss/108045/C%2B%2BJava-Union-Find-with-explanation-O(n)
https://leetcode.com/articles/redundant-connection-ii/
https://leetcode.com/problems/redundant-connection-ii/discuss/108046/most-posted-answers-are-wrong
In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of
edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.
Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.
Example 1:
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given directed graph will be like this: 1 / \ v v 2-->3
Example 2:
Input: [[1,2], [2,3], [3,4], [4,1], [1,5]] Output: [4,1] Explanation: The given directed graph will be like this: 5 <- 1 -> 2 ^ | | v 4 <- 3
Note:
http://www.cnblogs.com/grandyang/p/8445733.html
这道题是之前那道Redundant Connection的拓展，那道题给的是无向图，只需要删掉组成环的最后一条边即可，归根到底就是检测环就行了。而这道题给我们的是有向图，那么整个就复杂多了，因为有多种情况存在，比如给的例子1就是无环，但是有入度为2的结点3。再比如例子2就是有环，但是没有入度为2的结点。其实还有一种情况例子没有给出，就是既有环，又有入度为2的结点。好，我们现在就来总结一下这三种情况：
第一种：无环，但是有结点入度为2的结点（结点3）
[[1,2], [1,3], [2,3]]
1 / \ v v 2-->3
第二种：有环，没有入度为2的结点
[[1,2], [2,3], [3,4], [4,1], [1,5]]
5 <- 1 -> 2 ^ | | v 4 <- 3
第三种：有环，且有入度为2的结点（结点1）
[[1,2],[2,3],[3,1],[1,4]]
4 / v 1 / ^ v \ 2 -->3
对于这三种情况的处理方法各不相同，首先对于第一种情况，我们返回的产生入度为2的后加入的那条边[2, 3]，而对于第二种情况，我们返回的是刚好组成环的最后加入的那条边[4, 1]，最后对于第三种情况我们返回的是组成环，且组成入度为2的那条边[3, 1]。
明白了这些，我们先来找入度为2的点，如果有的话，那么我们将当前产生入度为2的后加入的那条边标记为second，前一条边标记为first。然后我们来找环，为了方便起见，找环使用联合查找Union Find的方法，可参见Redundant Connection中的解法三。当我们找到了环之后，如果first不存在，说明是第二种情况，我们返回刚好组成环的最后加入的那条边。如果first存在，说明是第三种情况，我们返回first。如果没有环存在，说明是第一种情况，我们返回second
X. Union Find
https://zxi.mytechroad.com/blog/graph/leetcode-685-redundant-connection-ii/
http://reeestart.me/2018/03/21/LeetCode-685-Redundant-Connection-II/
http://hehejun.blogspot.com/2017/09/leetcoderedundant-connection-ii.html
和之前题目不一样的是这道题目变成了有向图。那么变为有向图之后，我们对directed tree加上一条边和undirected tree有什么区别呢。可能会有以下三种状况：
- 仍然存在环，比如[1, 2], [2,3], [3,1]
- 不存在环但是存在某一个节点有两个父节点，比如[2,1], [3,1], [2, 3]
- 1和2的情况同时存在，比如[2,1], [3,1], [1,4], [4,2]
所以和I的解法不同，这里每一种情况我们都要判断并删除相应的边，具体算法如下：
- 如果是情况1，根据题目的要求，我们删除边e。e满足条件，按照题目给定的边的顺序依次加上边，当加上e的时候，第一次出现环
- 如果是情况2，删除一条通向v的边。v满足条件其有两个父节点。e满足条件其在题目给定的边的顺序中比另外一条通向v的边出现较后
- 如果是情况3，删除一条通向v的边。v满足条件其有两个父节点。e满足条件其在环上
我们只需要对这三种情况分别处理即可，DFS显然可以解，我们只需要记录环的路径（如果存在）和拥有两个父节点的v的对应的入射边（如果存在）。然后对于以上三种情况分别处理。但是DFS的解法需要我们建图。和I一样，我们可以用Union Find，这样省去了建图的步骤更为效率。在Union Find中我们也要对环和拥有两个父节点的v分别记录然后根据以上算法处理
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
vector<int> parents(edges.size() + 1, 0);
vector<int> roots(edges.size() + 1, 0);
vector<int> sizes(edges.size() + 1, 1);
vector<int> ans1;
vector<int> ans2;
for(auto& edge: edges) {
int u = edge[0];
int v = edge[1];
// A node has two parents
if (parents[v] > 0) {
ans1 = {parents[v], v};
ans2 = edge;
// Delete the later edge
edge[0] = edge[1] = -1;
}
parents[v] = u;
}
for(const auto& edge: edges) {
int u = edge[0];
int v = edge[1];
// Invalid edge (we deleted in step 1)
if (u < 0 || v < 0) continue;
if (!roots[u]) roots[u] = u;
if (!roots[v]) roots[v] = v;
int pu = find(u, roots);
int pv = find(v, roots);
// Both u and v are already in the tree
if (pu == pv)
return ans1.empty() ? edge : ans1;
// Unoin, always merge smaller set (pv) to larger set (pu)
if (sizes[pv] > sizes[pu])
swap(pu, pv);
roots[pv] = pu;
sizes[pu] += sizes[pv];
}
return ans2;
}
int find(int node, vector<int>& roots) {
while (roots[node] != node) {
roots[node] = roots[roots[node]];
node = roots[node];
}
return node;
}
This problem is very similar to "Redundant Connection". But the description on the parent/child relationships is much better clarified.
There are two cases for the tree structure to be invalid.
1) A node having two parents;
including corner case: e.g. [[4,2],[1,5],[5,2],[5,3],[2,4]]
2) A circle exists
If we can remove exactly 1 edge to achieve the tree structure, a single node can have at most two parents. So my solution works in two steps.
1) Check whether there is a node having two parents.
If so, store them as candidates A and B, and set the second edge invalid.
2) Perform normal union find.
If the tree is now valid
simply return candidate B
else if candidates not existing
we find a circle, return current edge;
else
remove candidate A instead of B. public int[] findRedundantDirectedConnection(int[][] edges) {
// can1 is before can2 and has higher priority
int[] can1 = {-1, -1};
int[] can2 = {-1, -1};
int[] roots = new int[edges.length + 1];
for (int[] edge : edges) {
int father = edge[0];
int child = edge[1];
if (roots[child] == 0) {
roots[child] = father;
} else if (roots[child] != 0) {
// the child already has father
// the newest link
can2 = new int[]{father, child};
// the older version of link
can1 = new int[]{roots[child], child};
// set the current link invalid
edge[1] = 0;
}
}
// reuse the roots matrix, do union find
for (int i = 0; i < roots.length; i++) {
roots[i] = i;
}
for (int[] edge : edges) {
int father = edge[0];
int child = edge[1];
if (child == 0) {
// current link is not valid
continue;
}
if (find(roots, father) == child) {
// there is a cycle
if (can1[0] == -1) {
// candidate not exist
return edge;
} else {
// candidate exist
return can1;
}
}
// union
roots[child] = father;
}
return can2;
}
private int find(int[] roots, int id) {
while (id != roots[id]) {
// path compression, optional
roots[id] = roots[roots[id]];
id = roots[id];
}
return id;
}
Starting from a rooted tree with
N-1 edges and N vertices, let's enumerate the possibilities for the added "redundant" edge. If there is no loop, then either one vertex must have two parents (or no edge is redundant.) If there is a loop, then either one vertex has two parents, or every vertex has one parent.
In the first two cases, there are only two candidates for deleting an edge, and we can try removing the last one and seeing if that works. In the last case, the last edge of the cycle can be removed: for example, when
1->2->3->4->1->5, we want the last edge (by order of occurrence) in the cycle 1->2->3->4->1 (but not necessarily 1->5).
Algorithm
We'll first construct the underlying graph, keeping track of edges coming from nodes with multiple parents. After, we either have 2 or 0
candidates.
If there are no candidates, then every vertex has one parent, such as in the case
1->2->3->4->1->5. From any node, we walk towards it's parent until we revisit a node - then we must be inside the cycle, and any future seen nodes are part of that cycle. Now we take the last edge that occurs in the cycle.
Otherwise, we'll see if the graph induced by
parent is a rooted tree. We again take the root by walking from any node towards the parent until we can't, then we perform a depth-first search on this root. If we visit every node, then removing the last of the two edge candidates is acceptable, and we should. Otherwise, we should remove the first of the two edge candidates.
In our solution, we use
orbit to find the result upon walking from a node x towards it's parent repeatedly until you revisit a node or can't walk anymore. orbit(x).node (or orbit(x)[0] in Python) will be the resulting node, while orbit(x).seen (or orbit(x)[1]) will be all the nodes visited.- Time Complexity: where is the number of vertices (and also the number of edges) in the graph. We perform a depth-first search.
- Space Complexity: , the size of the graph.
public int[] findRedundantDirectedConnection(int[][] edges) {
int N = edges.length;
Map<Integer, Integer> parent = new HashMap();
List<int[]> candidates = new ArrayList();
for (int[] edge : edges) {
if (parent.containsKey(edge[1])) {
candidates.add(new int[] { parent.get(edge[1]), edge[1] });
candidates.add(edge);
} else {
parent.put(edge[1], edge[0]);
}
}
int root = orbit(1, parent).node;
if (candidates.isEmpty()) {
Set<Integer> cycle = orbit(root, parent).seen;
int[] ans = new int[] { 0, 0 };
for (int[] edge : edges) {
if (cycle.contains(edge[0]) && cycle.contains(edge[1])) {
ans = edge;
}
}
return ans;
}
Map<Integer, List<Integer>> children = new HashMap();
for (int v : parent.keySet()) {
int pv = parent.get(v);
if (!children.containsKey(pv))
children.put(pv, new ArrayList<Integer>());
children.get(pv).add(v);
}
boolean[] seen = new boolean[N + 1];
seen[0] = true;
Stack<Integer> stack = new Stack();
stack.add(root);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!seen[node]) {
seen[node] = true;
if (children.containsKey(node)) {
for (int c : children.get(node))
stack.push(c);
}
}
}
for (boolean b : seen)
if (!b)
return candidates.get(0);
return candidates.get(1);
}
public OrbitResult orbit(int node, Map<Integer, Integer> parent) {
Set<Integer> seen = new HashSet();
while (parent.containsKey(node) && !seen.contains(node)) {
seen.add(node);
node = parent.get(node);
}
return new OrbitResult(node, seen);
}
}
class OrbitResult {
int node;
Set<Integer> seen;
OrbitResult(int n, Set<Integer> s) {
node = n;
seen = s;
}
}
https://leetcode.com/problems/redundant-connection-ii/discuss/108046/most-posted-answers-are-wrong
