# 0684. Redundant Connection
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/redundant-connection/
## 思路
遇到edge两个端点在一个group里面 就把ans改成这个edge
## Code

class Solution {
    int[] fa;
    int[] size;
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length+1;
        fa = new int[n];
        size = new int[n];
        for(int i=0; i<n; i++){
            fa[i] = i;
            size[i] = 1;
        }
        int[] ans = new int[2];
        for(int[] edge:edges){
            if(!combine(edge[0], edge[1])) ans = edge;
        }
        return ans;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        else return fa[a] = find(fa[a]);
    }
    private boolean combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return false;
        if(size[a]>size[b]){
            size[a]+=size[b];
            fa[b] = a;
        }
        else{
            size[b]+=size[a];
            fa[a] = b;
        }
        return true;
    }
}