684. 冗余连接(leetcode)

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

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        // 思路:遍历边,不断的加入相连的点到集合中,直到遍历到同在一集合的两个顶点位置,这个边就可以是答案
        init(edges.length);
        for(int[] edge:edges)
        {
            int a=edge[0],b=edge[1];
            if(find(a)==find(b))
            {
                return edge;
            }
            else union(a,b);
        }
        return null;
    }

    int[] p;
    void init(int n)
    {
        p=new int[n+1];
        for(int i=0;i<n;i++)p[i]=i;
    }
    int find(int x)
    {
        return x==p[x] ? x:(p[x]=find(p[x]));
    }
    void union(int x,int y)
    {
        p[find(x)]=find(y);
    }
}