Redundant Connection

并查集模板题

class Solution {
    class uf{
        int[] p;
        int n;
        public uf(int n){
            this.n = n + 1;
            this.p = new int[n + 1];
            for(int i = 1; i <= n; i++)
                this.p[i] = i;
        }
        public int find(int n){
            if(p[n] == n)
                return n;
            p[n] = find(p[n]);
            return p[n];
        }
        
        public void union(int a, int b){
            int ra = find(a);
            int rb = find(b);
            if(ra == rb)
                return;
            if(ra < rb)
                p[ra] = rb;
            else
                p[rb] = ra;
        }
    }
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        uf u = new uf(n);
        for(int[] e : edges){
            if(u.find(e[0]) != u.find(e[1]))
                u.union(e[0], e[1]);
            else
                return e;
        }
        return null;
    }
}