package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/redundant-connection/
 */
public class Problem684 {
    public int[] findRedundantConnection(int[][] edges) {
        UnionFind uf = new UnionFind();
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            if (uf.connected(a, b)) {
                return edges[i];
            }
            uf.union(a, b);
        }
        throw new RuntimeException("Should not happen");
    }

    private static class UnionFind {
        private final Map<Integer, Integer> map = new HashMap<>();

        public void union(int a, int b) {
            if (!map.containsKey(a)) {
                map.put(a, a);
            }
            if (!map.containsKey(b)) {
                map.put(b, b);
            }
            if (connected(a, b)) {
                return;
            }
            int value = map.get(a);
            for (Map.Entry<Integer, Integer> e : map.entrySet()) {
                if (e.getValue().equals(value)) {
                    map.put(e.getKey(), map.get(b));
                }
            }
        }

        public boolean connected(int a, int b) {
            if (!map.containsKey(a) || !map.containsKey(b)) {
                return false;
            }
            return map.get(a).equals(map.get(b));
        }
    }

    public static void main(String[] args) {
        Problem684 prob = new Problem684();
        System.out.println(Arrays.toString(prob.findRedundantConnection(new int[][]{
            {1, 2}, {1, 3}, {2, 3}
        }))); // [2,3]
        System.out.println(Arrays.toString(prob.findRedundantConnection(new int[][]{
            {1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}
        }))); // [1,4]
        System.out.println(Arrays.toString(prob.findRedundantConnection(new int[][]{
            {3, 4}, {2, 3}, {1, 2}, {1, 4}, {1, 5}
        }))); // [1,4]
        System.out.println(Arrays.toString(prob.findRedundantConnection(new int[][]{
            {3, 4}, {2, 3}, {1, 4}, {1, 2}, {1, 5}
        }))); // [1,2]
    }
}

@@ -16,82 +16,8 @@
 e;%0A%0A
-import java.util.Arrays;%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -564,29 +564,17 @@
 nal 
-Map%3C
 Integer
-, Integer%3E
+%5B%5D
  map
@@ -584,19 +584,21 @@
 new 
-HashMap%3C%3E()
+Integer%5B1001%5D
 ;%0A%0A 
@@ -654,35 +654,30 @@
     if (
-!
 map
-.containsKey(a)
+%5Ba%5D == null
 ) %7B%0A    
@@ -695,18 +695,15 @@
  map
-.put(a,
+%5Ba%5D =
  a
-)
 ;%0A  
@@ -730,35 +730,30 @@
     if (
-!
 map
-.containsKey(b)
+%5Bb%5D == null
 ) %7B%0A    
@@ -771,18 +771,15 @@
  map
-.put(b,
+%5Bb%5D =
  b
-)
 ;%0A  
@@ -890,23 +890,19 @@
 ue = map
-.get(a)
+%5Ba%5D
 ;%0A      
@@ -916,54 +916,38 @@
 or (
-Map.Entry%3CInteger, Integer%3E e :
+int i = 0; i %3C
  map.
+l
 en
-trySet()
+gth; i++
 ) %7B%0A
@@ -970,108 +970,68 @@
 if (
-e.getValue().equals(value)) %7B%0A                    map.put(e.getKey(), map.get(b));%0A                %7D
+map%5Bi%5D != null) %7B%0A                    if (map%5Bi%5D == value) %7B
 %0A   
@@ -1043,132 +1043,46 @@
     
-%7D%0A
       
-  %7D%0A%0A
       
-  public boolean connected(int a, int b) %7B%0A            if (!map.containsKey(a) %7C%7C !map.containsKey(b)) %7B%0A
+map%5Bi%5D = map%5Bb%5D;%0A         
     
@@ -1092,27 +1092,14 @@
     
- 
+%7D%0A
     
-return false;%0A
     
@@ -1124,45 +1124,9 @@
     
-return map.get(a).equals(map.get(b));
+%7D
 %0A   
@@ -1132,23 +1132,21 @@
       %7D%0A
+%0A
     
-%7D%0A%0A
     publ
@@ -1152,705 +1152,184 @@
 lic 
-static void main(String%5B%5D args) %7B%0A        Problem684 prob = new Problem684();%0A        System.out.println(Arrays.toString(prob.findRedundantConnection(new int%5B%5D%5B%5D%7B%0A            %7B1, 2%7D, %7B1, 3%7D, %7B2, 3%7D%0A        %7D))); // %5B2,3%5D%0A        System.out.println(Arrays.toString(prob.findRedundantConnection(new int%5B%5D%5B%5D%7B%0A            %7B1, 2%7D, %7B2, 3%7D, %7B3, 4%7D, %7B1, 4%7D, %7B1, 5%7D%0A        %7D))); // %5B1,4%5D%0A        System.out.println(Arrays.toString(prob.findRedundantConnection(new int%5B%5D%5B%5D%7B%0A            %7B3, 4%7D, %7B2, 3%7D, %7B1, 2%7D, %7B1, 4%7D, %7B1, 5%7D%0A        %7D))); // %5B1,4%5D%0A        System.out.println(Arrays.toString(prob.findRedundantConnection(new int%5B%5D%5B%5D%7B%0A            %7B3, 4%7D, %7B2, 3%7D, %7B1, 4%7D, %7B1, 2%7D, %7B1, 5%7D%0A        %7D))); // %5B1,2%5D
+boolean connected(int a, int b) %7B%0A            if (map%5Ba%5D == null %7C%7C map%5Bb%5D == null) %7B%0A                return false;%0A            %7D%0A            return map%5Ba%5D == map%5Bb%5D;%0A        %7D
 %0A   

Solve problem 684