LeetCode 685. Redundant Connection II
原题链接在这里:https://leetcode.com/problems/redundant-connection-ii/
题目:
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:
- 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.
题解:
If it is a invalid tree, there could be 2 cases:
- one node has 2 parents. [i, j], [k, j], two edges both point to j.
- there is cyrcle.
If remove one redundant edge could make it a valid tree.
If case 1 happens, then redundant edge must be either [i, j] or [k, j]. Otherwise, even you remove the redundant edge, [i, j] and [k, j] still point to the same node j and it is still invalid. Thus make them candidate 1 and candidate 2.
We check if cycle exists, if it exists, we check if case 1 happens or not. If no, then edge contecting 2 nodes already within the same union is the redundant edge likeRedundant Connection.
If yes, redundant edge is either candiate 1 or 2. First remove candidate 2 and check if cycle still exists, if no then answer is candidate 2, otherwise it is candidate 1.
Note: only update parent if parent[edge[1]] == 0.
Time Complexity: O(nlogn). find takes O(logn).
Space: O(n).
AC Java:
class Solution {
int [] parent; public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
parent = new int[n+1]; int [] can1 = new int[]{-1, -1};
int [] can2 = new int[]{-1, -1};
for(int i = 0; i<n; i++){
if(parent[edges[i][1]] == 0){
parent[edges[i][1]] = edges[i][0];
}else{
can2 = new int[]{edges[i][0], edges[i][1]};
can1 = new int[]{parent[edges[i][1]], edges[i][1]};
edges[i][1] = 0;
}
} for(int i = 0; i<=n; i++){
parent[i] = i;
} for(int [] edge : edges){
if(find(edge[0]) == find(edge[1])){
if(can1[0] == -1){
return edge;
} return can1;
} union(edge[0], edge[1]);
} return can2;
} private int find(int i){
if(i != parent[i]){
parent[i] = find(parent[i]);
} return parent[i];
} private void union(int i, int j){
int p = find(i);
int q = find(j);
parent[q] = p;
}
}
最新文章
- Spring 中classPath:用法
- [MySQL] 关系型数据库的设计范式 1NF 2NF 3NF BCNF
- 百度地图api根据定位获取附近商家(只获取屏幕内)
- OC - 15.NSURLSession与NSURLSessionTask
- php引用(&;)详解及注意事项
- (转)Windows重启延迟删除,重命名技术原理
- JS中window.document对象
- 错误 ;4 ;自定义工具错误: ;无法生成服务引用“DepartMentService”的代码。请检查其他错
- HDU 1028 Ignatius and the Princess III:dp or 母函数
- adb模拟操作之event
- centos7之NFS使用
- linux服务端日志中截取自己所需要的部分
- 终于懂得Perl句柄是什么意思了
- 【转载】许纪霖教授在上海财经大学演讲——漫谈“大学生的四个Learn”
- 2015-10-13 jQuery5实例
- Java面试知识点
- Java 实现删除文件工具类
- Shell-1--概念
- Lights inside a 3d Grid UVA - 11605(概率)
- spring学习 十四 注解AOP 通知传递参数