Redundant Connection — Leetcode 684

Original problem link: https://leetcode.com/problems/redundant-connection/description/

In this problem, we’re given a list of n edges in a graph with vertices labeled 1-n, where one or more of the edges is a redundant edge that creates a cycle in a graph that is otherwise a tree. The problem asks us to return the last edge in the input that can be removed to make a tree.

An intuitive way to do this is to write a DFS to detect whether there is a cycle in the graph and run the DFS with one edge removed (going backwards in the input) to detect the first edge that returns false (no cycle) and that visits all the vertices (to filter out the edge case where the graph is disconnected by the removal of the edge).

class Solution {

    boolean[] visited;

    public int[] findRedundantConnection(int[][] edges) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            if (graph.containsKey(edge[0])) {
                graph.get(edge[0]).add(edge[1]);
            } else {
                Set<Integer> neighbors = new HashSet<>();
                neighbors.add(edge[1]);
                graph.put(edge[0], neighbors);
            }
            if (graph.containsKey(edge[1])) {
                graph.get(edge[1]).add(edge[0]);
            } else {
                Set<Integer> neighbors = new HashSet<>();
                neighbors.add(edge[0]);
                graph.put(edge[1], neighbors);
            }
        }
        visited = new boolean[edges.length];
        
        for (int i = edges.length - 1; i >= 0; i--) {
            // try removing edge
            int v1 = edges[i][0];
            int v2 = edges[i][1];
            graph.get(v1).remove(v2);
            graph.get(v2).remove(v1);

            if (!dfs(graph, 1, -1) && allVisited(visited)) {
                return edges[i];
            }

            graph.get(v1).add(v2);
            graph.get(v2).add(v1);
            Arrays.fill(visited, false);
        }

        return null;
    }

    private boolean allVisited(boolean[] visited) {
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(Map<Integer, Set<Integer>> graph, int vertex, int prev) {
        Set<Integer> neighbors = graph.get(vertex);
        visited[vertex - 1] = true;

        for (int neighbor : neighbors) {
            if (visited[neighbor - 1] && neighbor != prev) {
                // there is a cycle
                return true;
            } else if (!visited[neighbor - 1]) {
                boolean result = dfs(graph, neighbor, vertex);
                if (result) {
                    return result;
                }
            }
        }
        return false;
    }
}

This solution beats about 30% of submissions with 6 ms of runtime.

Another way to approach this problem is to use union find, where connected vertices are gradually merged into the same group until we find an edge where the two vertices are already in the same group (meaning that this edge should be removed to create a tree).

class Solution {

    int[] representatives;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        representatives = new int[n];
        for (int i = 0; i < n; i++) {
            // initially every vertex is not connected
            representatives[i] = i + 1;
        }

        for (int[] edge : edges) {
            int vertex1 = edge[0];
            int vertex2 = edge[1];

            if (!isConnected(vertex1, vertex2)) {
                // make them connected (same group)
                union(vertex1, vertex2);
            } else {
                // found the edge to remove that's last in the input
                return edge;
            }
        }

        // shouldn't happen
        return new int[]{-1, -1};
    }

    private int find(int vertex) {
        if (representatives[vertex - 1] == vertex) {
            return vertex;
        }

        return find(representatives[vertex - 1]);
    }

    private void union(int vertex1, int vertex2) {
        int rep1 = find(vertex1);
        int rep2 = find(vertex2);

        if (rep1 == rep2) {
            return;
        }

        representatives[rep1 - 1] = rep2;
    }

    private boolean isConnected(int vertex1, int vertex2) {
        return find(vertex1) == find(vertex2);
    }
}

This solution beats 89%-100% of submissions with 0–1 ms of runtime.