leetcode-cn Daily Challenge on January 13th, 2021.
Difficulty : Medium
Related Topics : Tree、Union Find、Graph
In this problem, a tree is an undirected graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional 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 ofedges
is a pair[u, v]
withu < v
, that represents an undirected edge connecting nodesu
andv
.Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge
[u, v]
should be in the same format, withu < v
.Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / \ 2 - 3
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] Output: [1,4] Explanation: The given undirected graph will be like this: 5 - 1 - 2 | | 4 - 3
- 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.
We have overhauled the problem description + test cases and specified clearly the graph is an undirected graph. For the directed graph follow up please see Redundant Connection II. We apologize for any inconvenience caused.
- mine
- Java
- UnionFind
Runtime: 1 ms, faster than 64.33%, Memory Usage: 39.6 MB, less than 36.58% of Java online submissions
// O(N)time // O(N)space public int[] findRedundantConnection(int[][] edges) { int[] res = new int[2]; int max = 0; for(int[] e : edges){ max = Math.max(e[1], max); } UF uf = new UF(max); for(int[] e : edges){ if(!uf.union(e[0] - 1, e[1] - 1)){ res = e; } } return res; } class UF{ int[] arr; int count; public UF(int n){ count = n; arr = new int[n]; for(int i = 0; i < n; i++){ arr[i] = i; } } boolean union(int a, int b){ if(find(a) != find(b)){ arr[find(a)] = b; count--; return true; } return false; } int find(int a){ if(arr[a] != a){ arr[a] = find(arr[a]); } return arr[a]; } }
- UnionFind
- Java
- the most votes
- UnionFind
Runtime: 1 ms, faster than 70.87%, Memory Usage: 40 MB, less than 49.64% of Java online submissions
// O(N)time // O(N)space public int[] findRedundantConnection(int[][] edges) { int[] parent = new int[2001]; for (int i = 0; i < parent.length; i++) parent[i] = i; for (int[] edge: edges){ int f = edge[0], t = edge[1]; if (find(parent, f) == find(parent, t)) return edge; else parent[find(parent, f)] = find(parent, t); } return new int[2]; } private int find(int[] parent, int f) { if (f != parent[f]) { parent[f] = find(parent, parent[f]); } return parent[f]; }