【Number of Provinces】leetcode 解题 2/26

前言

早上好，
最近蛮喜欢写union find的题目，感觉大致都一样，但会有些变化

题目连结

解题

大致跟上一篇一样（Find_ function跟merge 一模一样），只是改了一些 main(findCircleNum)里的东西

具体更改

如果与自己连结的点已经出现父节点，那就把这个点加入(连结)至该父节点，否则就指定自己为父节点如果自己(该点)已经有连结，加入连结的点，否则指定自己为父节点查找每个点连结的父节点，查看有几个父节点

code连结

class Solution {public:    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];    }    int findCircleNum(vector<vector<int>>& isConnected) {        int n = isConnected.size();        vector<int> f(n),rank(n);        for(int i = 0;i < n;i++){            f[i] = i;            rank[i] = 1;        }                map<int,int> have;        for(int i = 0;i < n;i++){            for(int j = 0;j < n;j++){                if(i != j && isConnected[i][j] == 1){                    // if have j root                    if(have.count(j)){                        merge(f,rank,i,have[j]);                    }                    else{                        have[j] = i;                    }                }            }            if(have.count(i)){                merge(f,rank,i,have[i]);            }            else{                have[i] = i;            }        }        set<int> ans;        //find root        for(int i = 0;i < n;i++){            ans.insert(Find_(f,i));        }        return ans.size();    }};