package leetcode;

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

/**
 * https://leetcode.com/problems/redundant-connection/
 */
public class Problem684 {
    public int[] findRedundantConnection(int[][] edges) {
        // TODO
        return new int[0];
    }

    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) {
            return map.get(a).equals(map.get(b));
        }
    }

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

@@ -12,16 +12,41 @@
 tcode;%0A%0A
+import java.util.Arrays;%0A
 import j
@@ -245,41 +245,333 @@
     
-// TODO%0A        return new int%5B0%5D
+UnionFind uf = new UnionFind();%0A        for (int i = 0; i %3C edges.length; i++) %7B%0A            int a = edges%5Bi%5D%5B0%5D;%0A            int b = edges%5Bi%5D%5B1%5D;%0A            if (uf.connected(a, b)) %7B%0A                return edges%5Bi%5D;%0A            %7D%0A            uf.union(a, b);%0A        %7D%0A        throw new RuntimeException(%22Should not happen%22)
 ;%0A  
@@ -906,17 +906,16 @@
     if (
-!
 connecte
@@ -1253,32 +1253,138 @@
 int a, int b) %7B%0A
+            if (!map.containsKey(a) %7C%7C !map.containsKey(b)) %7B%0A                return false;%0A            %7D%0A
             retu
@@ -1542,32 +1542,48 @@
 tem.out.println(
+Arrays.toString(
 prob.findRedunda
@@ -1650,24 +1650,25 @@
 %0A        %7D))
+)
 ; // %5B2,3%5D%0A 
@@ -1685,32 +1685,48 @@
 tem.out.println(
+Arrays.toString(
 prob.findRedunda
@@ -1805,32 +1805,33 @@
 , 5%7D%0A        %7D))
+)
 ; // %5B1,4%5D%0A     
@@ -1844,32 +1844,48 @@
 tem.out.println(
+Arrays.toString(
 prob.findRedunda
@@ -1964,32 +1964,33 @@
 , 5%7D%0A        %7D))
+)
 ; // %5B1,4%5D%0A     
@@ -2011,16 +2011,32 @@
 println(
+Arrays.toString(
 prob.fin
@@ -2131,16 +2131,17 @@
      %7D))
+)
 ; // %5B1,

Update problem 684