Java BFS Edge Removal
Find the node that has only edge, remove that edge and node, then look again to find node with one edge. Remove all of them until can\'t find node with one edge
Find the node that has only edge, remove that edge and node, then look again to find node with one edge. Remove all of them until can\'t find node with one edge anymore. Now what\'s left in the graph is a circle, all the edges (connections) remaining will be a valid choice.\n\n```\n1 - 2 - 3 - 4\n        |   |\n        5 - 6\n\t\t\t\t\n    2 - 3 - 4\n        |   |\n        5 - 6\n\t\t\t\t\n        3 - 4\n        |   |\n        5 - 6\n```\n\n```\nclass Solution {\n    \n    public int[] findRedundantConnection(int[][] edges) {\n        Map<Integer, Set<Integer>> map = new HashMap<>();\n        for (int[] edge : edges) {\n            if (!map.containsKey(edge[0])) map.put(edge[0], new HashSet<>());\n            if (!map.containsKey(edge[1])) map.put(edge[1], new HashSet<>());\n            map.get(edge[0]).add(edge[1]);\n            map.get(edge[1]).add(edge[0]);\n        }\n        Queue<Integer> q = new LinkedList<>();\n        for (int key : map.keySet()) {\n            if (map.get(key).size() == 1) q.offer(key);\n        }\n        while (!q.isEmpty()) {\n            int node = q.poll();\n            Set<Integer> set = map.get(node);\n            map.remove(node);\n            for (int neighbor : set) {\n                map.get(neighbor).remove(node);\n                if (map.get(neighbor).size() == 1) q.offer(neighbor);\n            }\n        }\n        for (int i = edges.length - 1; i >= 0; i--) {\n            int[] edge = edges[i];\n            if (map.containsKey(edge[0]) &&  map.containsKey(edge[1])) return edge;\n        }\n        return new int[]{};\n    }\n    \n}\n```
[]