【Redundant Connection】leetcode 解题 2/27

今天也是写union find 的题目，好累～～

解题

题目要我们找到一个图形里面由许多线串连，哪一条线是多余的（只有一条，有两项输出最后进来的），简单来说就是去掉哪一条线图形依旧能串连

利用union find去找父节点，如果有一条线的两点都指向同一个父节点，就能判是多余的线了

建立union find function (Find_ 与 merge)依序填入与搜寻父节点回传最后一个传入的重複线段

然后就runtime error 了

（因为没有看到他是从 1 开始

code

code 连结

//Redundant Connection//midclass Solution {    int Find_(vector<int> &f,int x){        if(f[x] != x){            f[x] = Find_(f,f[x]);        }        return f[x];    }    void merge(vector<int> &f,vector<int> &rank,int x,int y){        x = Find_(f,x);        y = Find_(f,y);        if(x==y)return;        if(x < y){            swap(x,y);        }        f[y] = x;        rank[x] += rank[y];    }public:    vector<int> findRedundantConnection(vector<vector<int>>& edges) {            int n = edges.size();        vector<int> f(n+1),rank(n+1);        for(int i = 0;i <= n;i++){            f[i] = i;            rank[i] = 1;        }        map<int,int> have;        vector<vector<int>> ans;            for(int i = 0;i<n;i++){            int a = edges[i][0],b = edges[i][1];                        if(!have.count(a) && !have.count(b)){                have[a] = a;                have[b] = b;                f[a] = a;                f[b] = a;            }            else if(!have.count(a) && have.count(b)){                have[a] = b;                f[a] = b;            }            else if(have.count(a) && !have.count(b)){                have[b] = b;                f[b] = a;            }            else{                int c1 = Find_(f,a);                int c2 = Find_(f,b);                if(c1 == c2){                    ans.push_back({a,b});                }                else{                    merge(f,rank,a,b);                }            }        }        return ans.back();    }};