概念

题目

LC 0684. 冗余连接

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

并查集，只要找到哪条边导致了出现了环

class Solution {
private:
    int f[1001];
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        for(int i = 1; i <= 1000; i++) f[i] = i;

        for(auto t: edges){
            int x = t[0], y = t[1];

            if(find(x) != find(y)){
                f[find(x)] = find(y);
            }else{
                return {x, y};
            }
        }
        return {};
    }

    int find(int x){
        return f[x] == x ? x : find(f[x]);
    }
};