684. 冗余连接

思路：

如果在一棵树上加一条边会破坏树的性质，所以什么是一棵树的性质？

树的两个节点之间有且仅有一条唯一路径，换句话说就是一个没有环的连通图

所以很明显利用这一性质，题目中又提到返回最后一条冗余的边，所以我们正常按顺序处理连通关系就可以

并查集模板题

Solutions：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int fa[1010];
int find(int i){
    return (fa[i]==i?i:fa[i]=find(fa[i]));
}
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n=edges.size();
        auto merge=[&](int x,int y){
            if(find(x)==find(y))return false;
            else{
                fa[find(x)]=find(y);
                return true;
            }
        };
        for(int i=1;i<=n;++i)fa[i]=i;
        for(int i=0;i<n;++i){
            int x=edges[i][0],y=edges[i][1];
            if(!merge(x,y)){
                vector<int>ans={x,y};
                return ans;
            }
        }
        return {};
    }
};