684. Redundant Connection

https://leetcode.com/problems/redundant-connection/

https://leetcode.com/problems/redundant-connection/discuss/277026/DFS-Java-Solution-With-Explanation
DFS

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int[] ret = null;
        List<Set<Integer>> adjList = new ArrayList<>(1001);
        for(int i=0; i < 1001; i++)
            adjList.add(new HashSet<>());
        
        for(int[] edge : edges){
            int u = edge[0], v = edge[1];
            if(dfs(u, v, 0, adjList)){
                ret = edge;
            }else{
                adjList.get(u).add(v);
                adjList.get(v).add(u);
            }
        }
        return ret;
    }
    
    private boolean dfs(int u, int v, int pre, List<Set<Integer>> adjList){    
        if(u == v) return true; //find a path, the cycle exists
        for(int w : adjList.get(u)){
            //to avoid exploring the same edge from both the ends, 
            //we can pass in the current parent pre down the stack calls.
            if(w == pre) continue;
            if(dfs(w, v, u, adjList)) return true;
        }
        return false;
    }
}

https://leetcode.com/problems/redundant-connection/discuss/123819/Union-Find-with-Explanations-(Java-Python)
Union-Find

import java.util.*;

public class UnionFind {
    public static 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();
        // return new int[2];
    }

    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
        }

        // 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;
        }
    }
    public static void main(String[] args) {
        int[][] edges = {{1,2},{1,3},{2,3}};
        System.out.println(Arrays.toString(findRedundantConnection(edges)));
    }
}