LeetCode 684 - Redundant Connection


https://leetcode.com/problems/redundant-connection/description/
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 of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
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, with u < v.
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3
Example 2:
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
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.

  • X. Union-Find
    https://leetcode.com/problems/redundant-connection/discuss/123819/Union-Find-with-Explanations-(Java-Python)
        public int[] findRedundantConnection(int[][] edges) {
            DisjointSet disjointSet = new DisjointSet(edges.length);
            
            for (int[] edge : edges) {
                if (!disjointSet.union(edge[0] - 1, edge[1] - 1)) return edge;
            }
            
            throw new IllegalArgumentException();
        }
        
        static class DisjointSet {
            
            private int[] parent;
            private byte[] rank;
            
            public DisjointSet(int n) {
                if (n < 0) throw new IllegalArgumentException();
                parent = new int[n];
                rank = new byte[n];
            }
            
            public int find(int x) {
                if (parent[x] == 0) return x;
                return parent[x] = find(parent[x]); // Path compression by halving.
            }
            
            // Return false if x, y are connected.
            public boolean union(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX == rootY) return false;
                
                // Make root of smaller rank point to root of larger rank.
                if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
                else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
                else {
                    parent[rootX] = rootY;
                    rank[rootY]++;
                }
                
                return true;
            }
        }

    https://leetcode.com/problems/redundant-connection/discuss/107984/10-line-Java-solution-Union-Find.
        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];
        }
    


    If we are familiar with a Disjoint Set Union (DSU) data structure, we can use this in a straightforward manner to solve the problem: we simply find the first edge occurring in the graph that is already connected. The rest of this explanation will focus on the details of implementing DSU.
    A DSU data structure can be used to maintain knowledge of the connected components of a graph, and query for them quickly. In particular, we would like to support two operations:
    • dsu.find(node x), which outputs a unique id so that two nodes have the same id if and only if they are in the same connected component, and:
    • dsu.union(node x, node y), which draws an edge (x, y) in the graph, connecting the components with id find(x) and find(y) together.
    To achieve this, we keep track of parent, which remembers the id of a smaller node in the same connected component. If the node is it's own parent, we call this the leader of that connected component.
    • Time Complexity: O(N\alpha(N)) \approx O(N), where N is the number of vertices (and also the number of edges) in the graph, and \alpha is the Inverse-Ackermann function. We make up to N queries of dsu.union, which takes (amortized) O(\alpha(N)) time. Outside the scope of this article, it can be shown why dsu.union has O(\alpha(N)) complexity, what the Inverse-Ackermann function is, and why O(\alpha(N)) is approximately O(1).
    • Space Complexity: O(N). The current construction of the graph (embedded in our dsu structure) has at most N nodes.
        int MAX_EDGE_VAL = 1000;

        public int[] findRedundantConnection(int[][] edges) {
            DSU dsu = new DSU(MAX_EDGE_VAL + 1);
            for (int[] edge: edges) {
                if (!dsu.union(edge[0], edge[1])) return edge;
            }
            throw new AssertionError();
        }
    }

    class DSU {
        int[] parent;
        int[] rank;

        public DSU(int size) {
            parent = new int[size];
            for (int i = 0; i < size; i++) parent[i] = i;
            rank = new int[size];
        }

        public int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        public boolean union(int x, int y) {
            int xr = find(x), yr = find(y);
            if (xr == yr) {
                return false;
            } else if (rank[xr] < rank[yr]) {
                parent[xr] = yr;
            } else if (rank[xr] > rank[yr]) {
                parent[yr] = xr;
            } else {
                parent[yr] = xr;
                rank[xr]++;
            }
            return true;
        }
    https://leetcode.com/problems/redundant-connection/discuss/107984/10-line-Java-solution-Union-Find.
        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];
        }

    X.
    For each edge (u, v), traverse the graph with a depth-first search to see if we can connect u to v. If we can, then it must be the duplicate edge.
    • Time Complexity: O(N^2) where N is the number of vertices (and also the number of edges) in the graph. In the worst case, for every edge we include, we have to search every previously-occurring edge of the graph.
    • Space Complexity: O(N). The current construction of the graph has at most N nodes.

       Set<Integer> seen = new HashSet();
        int MAX_EDGE_VAL = 1000;

        public int[] findRedundantConnection(int[][] edges) {
            ArrayList<Integer>[] graph = new ArrayList[MAX_EDGE_VAL + 1];
            for (int i = 0; i <= MAX_EDGE_VAL; i++) {
                graph[i] = new ArrayList();
            }

            for (int[] edge: edges) {
                seen.clear();
                if (!graph[edge[0]].isEmpty() && !graph[edge[1]].isEmpty() &&
                        dfs(graph, edge[0], edge[1])) {
                    return edge;
                }
                graph[edge[0]].add(edge[1]);
                graph[edge[1]].add(edge[0]);
            }
            throw new AssertionError();
        }
        public boolean dfs(ArrayList<Integer>[] graph, int source, int target) {
            if (!seen.contains(source)) {
                seen.add(source);
                if (source == target) return true;
                for (int nei: graph[source]) {
                    if (dfs(graph, nei, target)) return true;
                }
            }
            return false;
        }


    X.
    public int[] findRedundantConnection(int[][] edges) {
    Map<Integer, Set<Integer>> graph = buildGraph(edges);
    LinkedHashSet<Integer> path = new LinkedHashSet<>();
    Integer cycleNode = findCycle(graph, 1, -1, path);
    System.out.println(path);
    keepCycleNodesOnly(path, cycleNode);
    System.out.println(path);
    for (int i = edges.length - 1; i >= 0; i--) {
    if (path.contains(edges[i][0]) && path.contains(edges[i][1])) {
    return edges[i];
    }
    }
    // should not happen
    throw new AssertionError();
    }

    private void keepCycleNodesOnly(LinkedHashSet<Integer> path, Integer cycleNode) {
    Iterator<Integer> it = path.iterator();
    while (it.hasNext()) {
    Integer curNode = it.next();
    if (!Objects.equals(curNode, cycleNode)) {
    it.remove();
    } else {
    break;
    }
    }
    }

    private Integer findCycle(Map<Integer, Set<Integer>> graph, int curNode, int prevNode,
    LinkedHashSet<Integer> path) {
    if (path.contains(curNode)) {
    return curNode;
    }

    path.add(curNode);
    if (graph.get(curNode) != null) {
    for (Integer nb : graph.get(curNode)) {
    // BUG: a-b b-a case
    if (nb == prevNode)
    continue;
    Integer circleNode = findCycle(graph, nb, curNode, path);
    if (circleNode != null) {
    return circleNode;
    }
    }
    }
    path.remove(curNode);
    return null;
    }

    private Map<Integer, Set<Integer>> buildGraph(int[][] edges) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for (int i = 0; i < edges.length; i++) {
    graph.computeIfAbsent(edges[i][0], li -> new HashSet<>()).add(edges[i][1]);
    graph.computeIfAbsent(edges[i][1], li -> new HashSet<>()).add(edges[i][0]);
    }
    return graph;

    }







    Labels

    LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

    Popular Posts