//
// Created by 高森森 on 2022/2/6.
//

#ifndef LEETCODE_SOLUTION20_H
#define LEETCODE_SOLUTION20_H
#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>

using namespace std;

class Solution20 {
public:
    int find(int x,vector<int>&fa){
        if(x==fa[x])
            return x;
        else{
            fa[x]=find(fa[x],fa);
            return fa[x];
        }
    }
    void merge(int i,int j,vector<int>&fa,vector<int>&rank){
        int x=find(i,fa);
        int y=find(j,fa);
        if(rank[x]<=rank[y]){
            fa[x]=fa[y];
        }else{
            fa[y]=fa[x];
        }
        if(rank[x]==rank[y]&&x!=y){
            rank[y]++;
        }
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
       //注意原本一棵树有n个节点，n-1条边，题目中添一条边之后变成n条边
        int n=edges.size()+1;
        vector<int>fa(n);
        for(int i=0;i<n;i++)
            fa[i]=i;
        vector<int>rank(n,1);
        for(auto edge:edges){
            int n1=edge[0];
            int n2=edge[1];
            if(find(n1,fa)!=find(n2,fa)){
                merge(n1,n2,fa,rank);
            }else{
                return edge;
            }
        }
        return vector<int>{};
    }
};


#endif //LEETCODE_SOLUTION20_H